Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/29: Рейтинг темы: голосов - 29, средняя оценка - 5.00
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 25
1

алгоритм Шелла

11.10.2012, 00:28. Показов 5794. Ответов 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;
      }
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.10.2012, 00:28
Ответы с готовыми решениями:

Алгоритм Шелла
Приветствую, CyberForum. Пересмотрел много видео про Алгоритм Шелла, где плясали и роботы...

Реализовать алгоритм Шелла
Очень прошу сильно помочь с сим заданием, сам я не могу, а очень надо ( Задача: Имеется...

Алгоритм сортировки Шелла
Расписать по шагам сортровку массива с помощью алгоритма сортировки...

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

6
Master of Orion
Эксперт .NET
6088 / 4944 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
11.10.2012, 00:51 2
rostik123456789, сделай слияния или хоара, но чтоб не заметили
0
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 25
11.10.2012, 01:09  [ТС] 3
я не очень знаю алгоритм сортировки слиянием ...
а хоара сразу видно будет ...
0
Master of Orion
Эксперт .NET
6088 / 4944 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
11.10.2012, 02:03 4
rostik123456789, на википедии гуглится за 5 минут Хотя если ОЧЕНь хочется - пишете отдельную функцию и табулированием загоняете за пределы экрана. А потом незаметно это функцию где-нидудь вызываете, хотя вызов тоже можете спрятать)
0
Эксперт С++
4259 / 2233 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2012, 08:15 5
Цитата Сообщение от rostik123456789 Посмотреть сообщение
как увеличить скорость этого алгоритма Шелла в 2 раза ....

Не по теме:

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

0
78 / 78 / 6
Регистрация: 18.06.2009
Сообщений: 533
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;
Попробуй так замерять...
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
30454 / 16825 / 3463
Регистрация: 12.02.2012
Сообщений: 28,198
Записей в блоге: 5
11.10.2012, 09:45 7
Цитата Сообщение от rostik123456789 Посмотреть сообщение
Кнут просто подобрал номера h для увеличения скорости сортровки.
- не "Кнут подбирал", а доказано, что скорость зависит от последовательности. В частности самая "плохая" последовательность - это 16,8,4,2,1
А самая "хорошая" зависит от сортируемых данных. Вот что пишет Википедия:

"эмпирическая последовательность Марцина Циура {1, 4, 10, 23, 57, 132, 301, 701, 1750}; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов"
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.10.2012, 09:45

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

Сравнение алгоритмов сортировки ... алгоритм Шелла
Вопрос такой, для лабораторной работы нужно сравнить три алгоритма сортировки чисел ... так вот...

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru