Сортировка методом Шелла

Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.

Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11,4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15,4-8-12-16. Выполняется сортировка в каждой четверке.

Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.

Примеры реализации

Pascal

procedure sort_shell (var a:array of word);
var
  bis,i,j,k:longint;
  h:word;
begin
  bis:=high(a);
  k:=bis shr 1; 
  While k>0 do
  Begin
    For i:=0 To bis-k do
    begin
      j:=i;
      While (j>=0) And  (a[j]>a[j+k]) do
      begin
        h:=a[j];
        a[j]:=a[j+k];
        a[j+k]:=h;
        dec(j,k);
      end;
    end;
    k:=k shr 1; 
  End;
End;

Глагол

ЗАДАЧА Шелл(a+: РЯД ИЗ ЦЕЛ);
ПЕР
  b,i,j,k,h: ЦЕЛ;
УКАЗ
  b:=РАЗМЕР(a)-1;
  k:=b ДЕЛИТЬ 2; 
  ПОКА k>0 ВЫП
    ОТ i:=0 ДО b-k ВЫП
      j:=i;
      ПОКА (j>=0) И (a[j]>a[j+k]) ВЫП
        h:=a[j];
        a[j]:=a[j+k];
        a[j+k]:=h;
        УМЕНЬШИТЬ(j,k)
      КОН;
    КОН;
    k:=k ДЕЛИТЬ 2 
  КОН
КОН Шелл;
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home