Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
#1

Заполнение массива методом Седжвика - C++

03.07.2012, 16:52. Просмотров 778. Ответов 1
Метки нет (Все метки)

Можно ли как-то заполнить массив методом Седжвика по другому, что бы не было столько нулей, сколько сейчас.(ну т.е. чтобы значительно меньше).

или если массив заполняется рандомно, то как сделать так, чтобы сортировка Шелла работала?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
 
//--------------------------------------------------------------------------------------------------------------------------
/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int increment(long inc[], long size) {
    int i = 0;
    inc[i] = 1;
 
    do {
        i++;
        inc[i] = 3*inc[i-1] + 1;
    } while (inc[i] < size);
 
    return (i < 2) ? 0 : i-2;
}
//--------------------------------------------------------------------------------------------------------------------------
template<class T>
void shellSort(T inc[], long size) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    long d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = increment(dseq, size);
 
    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];
 
        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < size; i++) {
            T tmp = inc[i];
            for (j = i-d; (j >= 0) && (inc[j] > tmp); j -= d) {
                inc[j+d] = inc[j];
            }
            inc[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}
 
void main ()
{   
    long a[1000] = {};
    increment(a, 1000);
    shellSort(a, 1000);
    for (int i = 0; i < 1000; i++)
        cout << a[i] << " ";
 
    _getch();
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 16:52     Заполнение массива методом Седжвика
Посмотрите здесь:

Книги Седжвика - C++
вечер добрый есть ли существенная разница между этими книгами? 1) http://www.ozon.ru/context/detail/id/1425749/ 2)...

6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика - C++
Разбираю 6-ю главу книги Роберт Седжвик: Фундаментальные алгоритмы C++. Части 1-4 Расматриваются простые методы сортировки, любых типов...

Заполнение массива - C++
Извините, что флудю, просто в старой теме уже не отвечают. data::data(int f){ if (f==1) ...

Заполнение массива - C++
Подскажите пожалуйста, как заполнить массив в такой закономерности: Например дано число 6:••• Пример для числа 4:••• ...

Заполнение массива - C++
Здравствуйте, помогите пожалуйста заполнить массив таким образом, или хотя бы подскажите алгоритм) Заранее благодарен...

Заполнение массива - C++
Привет народ! Очень нужна помощь срочно!(( Вот такое вот задание: 1,Составьте программу заполнения массива А(N,N) нулями и единицами в...

Заполнение массива - C++
Добрый день. Объясните,пожалуйста, следующий момент. Есть кусок кода: void fill(struct member *p){ printf(&quot;\nFill your name...

Заполнение массива - C++
Помогите, пожалуйста, решить такую задачу: Нужно заполнить массив 6*6 цифрами от 1 до 36 по следующей схеме: 1 2 4 7 11 16 3 ...

Заполнение массива от 'А' до 'Я' и 'а' до 'я' - C++
Как заполнить массив буквами русского алфавита по порядку, желательно не вручную . Нужно от 'А' до 'Я' и затем от 'а' до 'я' т.е 66...

Заполнение массива - C++
Даны числа от 0 до 15 (включительно), нужно записать их в одномерный массив в рандомном порядке, при этом числа не должны повторяться ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
03.07.2012, 19:55     Заполнение массива методом Седжвика #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <conio.h>
#include <iostream>
 
//--------------------------------------------------------------------------------------------------------------------------
/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int increment(long inc[], long size) {
    int i = 0;
    inc[i] = 1;
 
    do {
        i++;
        inc[i] = abs(3*inc[i-1] + 1);
    } while (i < size);
 
    return (i < 2) ? 0 : i-2;
}
 
template<class T> void shellSort(T inc[], long size)
{
    for (int q = size-1; q >= 0; q--)
         for (int i = 0, d = q; i + d < size; i++)
             if (inc[i] < inc[i+d]) std::swap<T>(inc[i],inc[i+d]);
}
 
using namespace std;
 
int main()
{
    long a[1000] = {};
    increment(a, 1000);
    shellSort<long>(a, 1000);
    for (int i = 0; i < 1000; i++)
        cout << a[i] << " ";
 
    _getch();
 
    return 0;
}
http://liveworkspace.org/code/a608c6...96b9dae293601b
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru