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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
rostik123456789
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 25
#1

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

11.10.2012, 00:28. Просмотров 3154. Ответов 6
Метки нет (Все метки)

как увеличить скорость этого алгоритма Шелла в 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++
Приветствую, CyberForum. Пересмотрел много видео про Алгоритм Шелла, где плясали и роботы показывали наглядно как всё это делается, но...

Реализовать алгоритм Шелла - C++
Очень прошу сильно помочь с сим заданием, сам я не могу, а очень надо ( Задача: Имеется массив действительных чисел. Необходимо...

Алгоритм сортировки Шелла - C++
http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/21/2107.htm здесь сказано, что существует, некая последовательность...

Метод Шелла, алгоритм обмена - C++
Помогите написать программы. 1. Упорядочить заданный список целых значений методом Шелла. 2. Доно массив записей,каждый из которых...

Сравнение алгоритмов сортировки ... алгоритм Шелла - C++
Вопрос такой, для лабораторной работы нужно сравнить три алгоритма сортировки чисел ... так вот измеряю время работы : double start...

Считать с файла вещественные числа и отсортировать их в порядке убывания, используя алгоритм Шелла - C++
Считать с файла вещественные числа и отсортировать их в порядке убывания, используя алгоритм Шелла

ШЕЛЛА - C++
Нигде не могу найти сортировку методом Шелла. Сделал по схеме насси,но она не работает, исправьте, плиз: void shella(int mas,int n) ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Psilon
Master of Orion
Эксперт .NET
5882 / 4779 / 633
Регистрация: 10.07.2011
Сообщений: 14,399
Записей в блоге: 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
Эксперт .NET
5882 / 4779 / 633
Регистрация: 10.07.2011
Сообщений: 14,399
Записей в блоге: 5
Завершенные тесты: 4
11.10.2012, 02:03     алгоритм Шелла #4
rostik123456789, на википедии гуглится за 5 минут Хотя если ОЧЕНь хочется - пишете отдельную функцию и табулированием загоняете за пределы экрана. А потом незаметно это функцию где-нидудь вызываете, хотя вызов тоже можете спрятать)
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2012, 08:15     алгоритм Шелла #5
Цитата Сообщение от rostik123456789 Посмотреть сообщение
как увеличить скорость этого алгоритма Шелла в 2 раза ....

Не по теме:

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

Oxotnuk
77 / 77 / 2
Регистрация: 18.06.2009
Сообщений: 532
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++
Скажите пожалуйста какой из вариантов лучше использовать для реализации сортировки Шелла? Второй вариант меня смущает тем, что там больше...

Сортировка Шелла 2 - C++
Не могу понять в чём ошибка компиляции, подскажите пожалуйста) #include &lt;malloc.h&gt; #include &lt;stdio.h&gt; #include &lt;conio.h&gt; ...

Сортировка Шелла - C++
Здраствуйте! Обьясните пожалуйста сортировку Шелла ну или хотя бы скиньте код самой сортировки.

C++ Сортировка Шелла? - C++
Здравствуйте. Нужно написать сортировку Шелла, но они все так похожи, что не могу понять, правильная ли она у меня. Прошу помочь, она ли...


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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
22515 / 10920 / 1774
Регистрация: 12.02.2012
Сообщений: 18,067
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     алгоритм Шелла
Ответ Создать тему
Опции темы

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