Сортировка Шелла
В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сам метод объясняется и демонстрируется на стандартном примере. Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере восемь элементов и каждая группа состоит точно из двух элементов. После первого прохода элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на две позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец на третьем проходе идет обычная, или одинарная, сортировка.
На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок. Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает{так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Также, очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Однако совсем не очевидно, что такой прием "уменьшающихся расстояний" может дать лучшие результаты, если расстояния не будут степенями двойки. Поэтому приводимая ниже программа не ориентирована на некую определенную последовательность расстояний. Все t расстояний обозначаются соответственно h1, h2, … , ht, для них выполняются условия:
Ht = 1; Hi+1 < Hi
Каждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров. Ясно, что каждая из сортировок нуждается в постановке своего собственного барьера и программу для определения его местоположения необходимо делать насколько возможно простой. Поэтому приходится расширять массив не только на одну-единственную компоненту A0, а на h1 компонент. Его описание теперь выглядит так:
A:= ARRAY[-h1..n] OF item;
Сам алгоритм для t = 4 описывается процедурой ShellSort
PROCEDURE ShellSort;
CONST t = 4;
VAR i, j, k, s: index;
х: item; m: 1. .t;
h: АRRAУ [1 .. t] OF INTEGER:
BEGIN h[1] := 9; h[2] := 5; h[3] := 3; h[4] := l;
FOR m := 1 ТО t DO
k := h[m]; s := -k; (* место барьера *)
FOR i := k+1 ТО n DО
х := a[i]; j := i-k;
IF s = 0 THEN s := -k END;
s := s+1; а[5] := х; (* установка барьера *)
WНILE х < a[j] DО a[j+k] := a[j]; j := j-k END;
a[j+k]:= х
END
END
END ShellSort;
Анализ сортировки Шелла. Математический анализ показывает, что для сортировки n элементов методом Шелла затраты пропорциональны n1.2. Хотя это число значительно лучше, чем n в квадрате, тем не менее мы не ориентируемся в дальнейшем на этот метод, поскольку существуют алгоритмы ещё лучше.
2. Быстрая сортировка (quick sort).
