Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.10.2012, 00:28. Просмотров 3620. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2012, 00:28
Я подобрал для вас темы с готовыми решениями и ответами на вопрос алгоритм Шелла (C++):

Алгоритм Шелла - 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++
Считать с файла вещественные числа и отсортировать их в порядке убывания, используя алгоритм Шелла

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

Не по теме:

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

0
Oxotnuk
77 / 77 / 2
Регистрация: 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
Catstail
Модератор
23458 / 11585 / 1886
Регистрация: 12.02.2012
Сообщений: 18,914
11.10.2012, 09:45 #7
Цитата Сообщение от rostik123456789 Посмотреть сообщение
Кнут просто подобрал номера h для увеличения скорости сортровки.
- не "Кнут подбирал", а доказано, что скорость зависит от последовательности. В частности самая "плохая" последовательность - это 16,8,4,2,1
А самая "хорошая" зависит от сортируемых данных. Вот что пишет Википедия:

"эмпирическая последовательность Марцина Циура {1, 4, 10, 23, 57, 132, 301, 701, 1750}; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов"
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2012, 09:45
Привет! Вот еще темы с ответами:

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

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

Сортировка Шелла - C++
Здравствуйте. Решил сравнить скорость действия сортировки Шелла с различными последовательностями длин промежутков между элементами. Но...

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


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

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

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