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

 

Цель алгоритма – заставить каждый  сортируемый элемент за шаг вставки перемещаться большим скачком. Для этого исходный массив разбивается на группы специальным образом. Предположим в массиве 16 чисел (число кратное двойке взято только для удобства). Выполним разбиение массива на пары следующим образом: (a₁, a₉), (a₂, a₁₀)…. (a_8, a₁₆). Внутри каждой группы выполняем сортировку способом вставок. Затем переходим к следующему разбиению в котором элементы массива объединяются уже по 4 следующим образом (a_1, a₅, a₉, a₁₃), (a₄, a₈, a₁₂, a₁₆) и тд. То есть элементы отстоят друг от друга на 4 позиции. На следующем шаге соответственно на 2 позиции и на последнем на 1. Таким образом последовательность расстояний внутри групп в нашем примере такова 8, 4, 2, 1. Ясно, что такая последовательность невозможна для любого массива, но сортировка Шелла этого и не требует. Существенно важно только одно – последнее смещение должно быть равно 1, последовательность же может быть любой, при любой последовательности массив будет отсортирован, но выбор последовательности существенно влияет на скорость сортировки

 

Алгоритм

 

Будем считать последовательность смещений заданной. Некое смещение называется начальным. Очередной смещение назовем текущим.

 

Текущее смещение = Начальному

Пока Величина смещения больше нуля делать

              Для каждой Группы (при текущем смещении)

              Выполняем сортировку вставками

Перейти к следующему смещению

 

Описание алгоритма конечно коротковато, но краткость алгоритма надеемся скомпенсирована детальностью предварительного пояснения.

 

Текст программы

 

MODULE example;

IMPORT In, StdLog;

PROCEDURE Sort*;

VAR

  a:ARRAY 100 OF INTEGER;

  N,i,L,c,k,t,j:INTEGER;

BEGIN

 In.Open;

 N:=-1;

 REPEAT

  N:=N+1;

  In.Int(a[N]);

 UNTIL ~In.Done;

 L:=N DIV 2;

 WHILE L>=1 DO

   k:=0;

   (*Перебор групп для текущего шага*)

   WHILE k+L<=N - 1 DO (*Сортировка очередной группы*)

     i:=k;

     WHILE i<=N-1 DO

       (*Поиск своей позиции для очередного элемента*)

       t:=k;

       WHILE a[t]<a[i] DO

         t:=t+L;

       END;

       (*Вставка очередного элемента в свою позицию*)

       c:=a[i];

       j:=i;

       WHILE j>t DO

         a[j]:=a[j-L];

         j:=j-L;

       END;

       a[t]:=c;

       i:=i+L;

     END;

     k:=k+1;

   END;

   IF L=1 THEN

     L:=0;

   ELSE 

     L:=L DIV 2;

   END;

 END;

 FOR i:=0 TO N-1 DO

   StdLog.Int(a[i]);

 END;

END Sort;

END example.