В 1959 г. Д.Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Метод демонстрируется в таблице 2.1.Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4 позиции. Такой процесс называется 4-сортировкой. Рассмотрим пример из 8 элементов, где каждая группа состоит точно из двух элементов. После первого прохода элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на две позиции - и вновь сортируются. Это называется 2-сортировкой. И, наконец, на третьем проходе идет обычная или 1-сортировка.
На первый взгляд можно засомневаться: если необходимо несколько проходов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок.
Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущего только выигрывает (так как каждая i -сортировка объединяет две группы, уже отсортированные 2i -сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает последнюю работу. Однако совсем не очевидно, что такой прием «уменьшающихся расстояний» может дать лучшие результаты, если расстояния не будут степенями двойки. Поэтому приводимая программа не ориентирована на некую определенную последовательность расстояний.
Таблица 2.1.Сортировка с помощью включений с убывающими приращениями
4-сортировка:
2-сортировка:
1-сортировка:
Все t приращений обозначаются соответственно h1,…,ht, для них выполняются условия:
ht = 1, hi+1<hi
Каждая h -сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров. Ясно, что каждая из сортировок нуждается в постановке своего собственного барьера и программу для определения его местоположения необходимо делать насколько возможно простой. Поэтому приходится расширять массив не только на одну-единственную компоненту a [0], а на h1 компонент. Его описание теперь выглядит так:
a: ARRAY[-h1..n] OF item
Сам алгоритм для t = 4 описывается процедурой Shellsort в программе 2.1.
PROCEDURE ShellSort;
CONST t = 4;
VAR i, j, k, s: index; x: item; m:1..t;
h: ARRAY[1..t] OF INTEGER;
BEGIN h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=1;
FOR m:=1 TO t DO
BEGIN k:=h[m]; s:= -k; {место барьера}
FOR i: = k+1 TO n DO
BEGIN x:=a[i]; j:=i-k;
IF s=0 THEN s: = -k; s:=s+1; a[s]:=x;
WHILE x.key<a[j].key DO
BEGIN a [j +k]:=a[j]; j: =j-k
END;
a[j +k]:=x
END
END
END;
Программа 2.1. Сортировка Шелла
Анализ сортировки Шелла. Анализ этого алгоритма поставил несколько весьма трудных математических проблем, многие из которых так еще и не решены. В частности, не известно, какие приращения дают наилучшие результаты. Но вот удивительный факт: они не должны быть кратны друг другу. Это позволяет избежать явления уже очевидного из приведенного выше примера, когда при каждом проходе взаимодействуют две цепочки, которые до этого нигде еще не пересекались. И действительно, желательно, чтобы взаимодействие различных цепочек проходило как можно чаще. Справедлива такая теорема: если k - рассортированная последовательность i-сортируется, то она остается k - рассортированной. В своей работе Кнут показывает, что имеет смысл использовать такую последовательность (она записана в обратном порядке):1, 4, 13, 40, 121,…, где hk- 1= 3 hk +1, ht = 1 и t =[log3 n ]-1. Он рекомендует и другую последовательность: 1, 3, 7, 15, 31, …, где hk -1= 2 hk +1, ht = 1 и t =[log2 n ]-1.Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n. Хотя это число значительно лучше n 2, тем не менее, мы не ориентируемся в дальнейшем на этот метод, поскольку существуют еще лучшие алгоритмы.