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

алгоритм Шелла - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
rostik123456789
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 25
11.10.2012, 00:28     алгоритм Шелла #1
как увеличить скорость этого алгоритма Шелла в 2 раза ....

Где-то читал про Сортировку методом Шелла-Кнута.
Кнут просто подобрал номера h для увеличения скорости сортровкы.
Но я не знаю сделать методом Шелла-Кнута.

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
/ * Метод Кнута h (k-1) = 3 * h (k) +1, h (t) = 1, где
h (i) - шаг сортировки,
t = ln (n) / ln (3) -1 - число шагов сортировки,
n - длина списка * /
 
void sort_Shell(int *mass, int SIZE)
{
   int step = SIZE / 2;//инициализируем шаг.
    while (step > 0)//пока шаг не 0
    {
      for (int i = 0; i < (SIZE - step); i++)
            {
                 int j = i;
                 while (j >= 0 && mass[j] > mass[j + step])
                    {
                        int temp = mass[j];
                        mass[j] = mass[j + step];
                        mass[j + step] = temp;
                        j--; 
                    }
                }
           step = step / 2;
        }
}
Добавлено через 3 часа 13 минут
сделал, сортирует быстрее, но надо еще быстрее ...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sort_Shell(int *mass, int SIZE)
{
int step = SIZE / 2, i, j, tmp;
    while (step > 0) {
 
        for(i = step; i < SIZE; ++i) {
            tmp = mass[i];
 
            for(j = i - step; j >= 0 && mass[j] > tmp; j -= step) {
                mass[j+step] = mass[j];
 
            }
            mass[j+step] = tmp;
        }
        step /= 2;
      }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2012, 00:28     алгоритм Шелла
Посмотрите здесь:

Метод Шелла C++
C++ Метод Шелла
C++ Сравнение алгоритмов сортировки ... алгоритм Шелла
C++ ШЕЛЛА
Метод Шелла, алгоритм обмена C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
11.10.2012, 00:51     алгоритм Шелла #2
rostik123456789, сделай слияния или хоара, но чтоб не заметили
rostik123456789
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 25
11.10.2012, 01:09  [ТС]     алгоритм Шелла #3
я не очень знаю алгоритм сортировки слиянием ...
а хоара сразу видно будет ...
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
11.10.2012, 02:03     алгоритм Шелла #4
rostik123456789, на википедии гуглится за 5 минут Хотя если ОЧЕНь хочется - пишете отдельную функцию и табулированием загоняете за пределы экрана. А потом незаметно это функцию где-нидудь вызываете, хотя вызов тоже можете спрятать)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2012, 08:15     алгоритм Шелла #5
Цитата Сообщение от rostik123456789 Посмотреть сообщение
как увеличить скорость этого алгоритма Шелла в 2 раза ....

Не по теме:

как вариант, запустить на более мощном компьютере)

Oxotnuk
 Аватар для Oxotnuk
77 / 77 / 2
Регистрация: 18.06.2009
Сообщений: 526
11.10.2012, 08:28     алгоритм Шелла #6
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
float * shell(float * a,int n,bool amb)
{
    bool c;
    int e,g,i,j;
    float tmp;
    n = n-1;
    g = (n+1)/2;
    do
    {
        i = g;
        do
        {
            j = i-g;
            c = true;
            do
            {
                if(sravni(a[j]-1,a[j+g],amb))
                {
                    c = false;
                }
                else
                {
                    tmp = a[j];
                    a[j] = a[j+g];
                    a[j+g] = tmp;
                }
                j = j-1;
            }
            while(j>=0&&c);
            i = i+1;
        }
        while(i<=n);
        g = g/2;
    }
    while(g>0);
    return a;
Попробуй так замерять...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2012, 09:45     алгоритм Шелла
Еще ссылки по теме:

Алгоритм Шелла C++
C++ Алгоритм сортировки Шелла
Реализовать алгоритм Шелла C++

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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
11.10.2012, 09:45     алгоритм Шелла #7
Цитата Сообщение от rostik123456789 Посмотреть сообщение
Кнут просто подобрал номера h для увеличения скорости сортровки.
- не "Кнут подбирал", а доказано, что скорость зависит от последовательности. В частности самая "плохая" последовательность - это 16,8,4,2,1
А самая "хорошая" зависит от сортируемых данных. Вот что пишет Википедия:

"эмпирическая последовательность Марцина Циура {1, 4, 10, 23, 57, 132, 301, 701, 1750}; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов"
Yandex
Объявления
11.10.2012, 09:45     алгоритм Шелла
Ответ Создать тему
Опции темы

Текущее время: 22:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru