VPF::Алгоритм сортировки Шелла. Три-сортировка

BCworm

Дата 19.2.2008, 04:25 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 124
Регистрация: 23.8.2007

Репутация: нет
Всего: нет

Алгоритм сортировки Шелла. Три-сортировка

Знающие люди объясните пожалуйста что такое три-сортировка в методе Шелла
Если есть примеры до и пос ле такой сортировки
Уже полгугла перерыл везде одно и тоже и ничего по существу

SoWa

Дата 19.2.2008, 06:03 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Ничего особо страшного. Найди книжку Кормена "Алгоритмы: построение и анализ", там по именному указателю найдешь Шелла, откуда узнаешь, что его алгоритм- сортировка вставками, слегка модифицированная. На 19 странице если что smile

--------------------

Всем добра smile

BCworm

Дата 19.2.2008, 08:47 (ссылка)

(голосов:1)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 124
Регистрация: 23.8.2007

Репутация: нет
Всего: нет

Скачал книжку Кормена "Алгоритмы: построение и анализ" в надежде на 19 странице найти то что нужно но увы. Просмотрел оглавление тоже чего нужно не нашел. Сделал вывод если там и есть про сортировку Шелла( в принципе сомнений нет) то насчет три-сортировки не уверен.
Неужели никто не знает а?
Принцип какой хоть?

4d5a

Дата 12.3.2008, 16:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.6.2007

Репутация: 1
Всего: 1

В двух словах:
сортировка шелла- это модифицированная сортировка вставками, причем модификация заключается в том, что записи перемещаются бо'льшими скачками чем при вставке.
Вначале массив длины С делится на n групп, в каждой по (С div n) элементов, они отдельно сортируются, далее массив делится на n/2 групп и тд.

Прочитай про сортировку Шела.
Кнут, третий том на ~96 странице.

Думаю, что скорее всего, три-сортировка в методе Шелла это когда делитель не 2 а 3, хотя
слова "три-сортировка" не припомню.

Добавлено через 4 минуты и 34 секунды
те в общем случае приращение [http://algolist.manual.ru/sort/shell_sort.php] может быть любым, а 'три-' возможно указывает на конкретное значение.

Rusart

Дата 17.3.2008, 15:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 24
Регистрация: 1.2.2008

Репутация: нет
Всего: нет

Цитата

Procedure ShellaSort(var A:Array of integer; var N,S,P:integer);
var
  b,j,h,ss,pp:integer;
  begin
    S:=0;
    P:=0;
    h:=N;
    h:=h div 2;
    while h>1 do
    begin
      j:=0;
      while (j+h)<=n do
      begin
        inc(s);
        if A[j]>a[j+h] then
        begin
          b:=A[j];
          A[j]:=A[j+h];
          A[j+h]:=b;
          inc(p);
        end;
        inc(j);
      end;
      h:=h div 2;
      SS:=s;
      pp:=P;
    end;
    SimpleSelection(a,n,s,p);
    S:=SS+s;
    p:=pp+p;
  end;

Мой алгоритм шелла, как я сделал, вроде правильно! smile

а три шелла потому что наверное что 3 разных вида
1. H:=H div 2
2. h:= (h-1) div 3
3. h:= (h-1) div 2
Но я не уверен, если нужно я через две недели точно узнаю!

Это сообщение отредактировал(а) Rusart - 17.3.2008, 15:42

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »