Пример сортировки методом Шелл

В общем случае алгоритм Шелла естественно переформулируется для заданной последовательности из t расстояний между элементами h1, h2,..., ht, для которых выполняются условия h t = 1 и h _{(i + 1)} < h _i . Дональд Кнут показал, что при правильно подобранных t и h сложность алгоритма Шелла является O(n ^(1.2) ), что существенно меньше сложности простых алгоритмов сортировки.

На первый взгляд можно засомневаться; если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок,

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2 i -сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Однако совсем не очевидно, что такой прием «уменьшающихся расстояний» может дать лучшие результаты, если расстояния не будут степенями двойки. Поэтому приводимая программа не ориентирована на некую определенную последовательность расстояний. Каждая h-сортировка программируется как сортировка с помощью прямого включения.

k: = n;

WHILE k > 1 DO BEGIN

k: = k DIV 2;

FOR i: = k + 1 TO n DO BEGIN

x: = a[i]; j: = i;

WHILE (x < a[j – k]) AND (j> i – k) DO BEGIN

a[j]: = a[j – k];

j: = j – k;

END;

a [ j ]: = x;

END;

END;

Анализ сортировки Шелла. Анализ этого алгоритма поставил несколько весьма трудных математических проблем, многие из которых так еще и не решены. В частности, не известно, какие расстояния дают наилучшие результаты. Но вот удивительный факт: они не должны быть множителями один другого. Это позволяет избежать явления уже очевидного из приведенного выше примера, когда при каждом проходе взаимодействуют две цепочки, которые до этого нигде еще не пересекались. И действительно, желательно, чтобы взаимодействие различных цепочек проходило как можно чаще. Справедлива такая теорема: если k-отсортированную последовательность i-отсортировать, то она остается k-отсортированной. Кнут показывает, что имеет смысл использовать такую последовательность (она записана в обратном порядке): 1, 4, 13, 40, 121,..., где h _{k – 1} = 3 h _k + 1, h _t = 1 и t = (log ₃ n) – 1 (t - число расстояний). Он рекомендует и другую последовательность: 1, 3, 7, 15, 31,... где h _{k – 1} = 2 h _k + 1, h _t = 1 и t = (log ₂ n) – 1. Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n ^1.2 . Хотя это число значительно лучше n ² , тем не менее мы не ориентируемся в дальнейшем на этот метод, поскольку существуют еще лучшие алгоритмы.

Сортировка с помощью дерева (Heapsort)

Начнем с простого метода сортировки с помощью дерева, при использовании которого явно строится двоичное дерево сравнения ключей. Построение дерева начинается с листьев, которые содержат все элементы массива. Из каждой соседней пары выбирается наименьший элемент, и эти элементы образуют следующий (ближе к корню уровень дерева). Из каждой соседней пары выбирается наименьший элемент и т.д., пока не будет построен корень, содержащий наименьший элемент массива. Двоичное дерево сравнения для массива, используемого в наших примерах, показано на рисунке 5.1. Итак, мы уже имеем наименьшее значение элементов массива. Для того чтобы получить следующий по величине элемент, спустимся от корня по пути, ведущему к листу с наименьшим значением. В этой листовой вершине проставляется фиктивный ключ с «бесконечно большим» значением, а во все промежуточные узлы, занимавшиеся наименьшим элементом, заносится наименьшее значение из узлов - непосредственных потомков (рис. 5.2). Процесс продолжается до тех пор, пока все узлы дерева не будут заполнены фиктивными ключами (рисунки 5.3–5.8).

Рис. 5.1. Первый шаг

Рис. 5.2. Второй шаг

Рис. 5.3. Третий шаг

Рис. 5.4. Четвертый шаг

Рис. 5.5. Пятый шаг

Рис. 5.6. Шестой шаг

Рис. 5.7. Седьмой шаг

Рис. 5.8. Восьмой шаг

На каждом из n шагов, требуемых для сортировки массива, нужно log n (двоичный) сравнений. Следовательно, всего потребуется n log n сравнений, но для представления дерева понадобится 2n – 1 дополнительных единиц памяти.

Имеется более совершенный алгоритм, который принято называть пирамидальной сортировкой (Heapsort). Его идея состоит в том, что вместо полного дерева сравнения исходный массив a[1], a[2],..., a[n] преобразуется в пирамиду, обладающую тем свойством, что для каждого a[i] выполняются условия a[i] < = a[2i] и a[i] < = a[2i + 1]. Затем пирамида используется для сортировки.

Наиболее наглядно метод построения пирамиды выглядит при древовидном представлении массива, показанном на рисунке 5.9. Массив представляется в виде двоичного дерева, корень которого соответствует элементу массива a[1]. На втором ярусе находятся элементы a[2] и a[3]. На третьем - a[4], a[5], a[6], a[7] и т.д. Как видно, для массива с нечетным количеством элементов соответствующее дерево будет сбалансированным, а для массива с четным количеством элементов n элемент a[n] будет единственным (самым левым) листом «почти» сбалансированного дерева.

Рис. 5.9

Очевидно, что при построении пирамиды нас будут интересовать элементы a[n/2], a[n/2 – 1],..., a[1] для массивов с четным числом элементов и элементы a[(n – 1)/2], a[(n – 1)/2 – 1],..., a[1] для массивов с нечетным числом элементов (поскольку только для таких элементов существенны ограничения пирамиды). Пусть i - наибольший индекс из числа индексов элементов, для которых существенны ограничения пирамиды. Тогда берется элемент a[i] в построенном дереве и для него выполняется процедура просеивания, состоящая в том, что выбирается ветвь дерева, соответствующая min(a[2*i], a[2*i + 1]), и значение a[i] меняется местами со значением соответствующего элемента. Если этот элемент не является листом дерева, для него выполняется аналогичная процедура и т.д. Такие действия выполняются последовательно для a[i], a[i – 1],..., a[1]. Легко видеть, что в результате мы получим древовидное представление пирамиды для исходного массива (последовательность шагов для используемого в наших примерах массива показана на рисунках 5.10–5.13).

Рис. 5.10

Рис. 5.11

Рис. 5.12

Рис. 5.13

В 1964 г. Флойд предложил метод построения пирамиды без явного построения дерева (хотя метод основан на тех же идеях). Построение пирамиды методом Флойда для нашего стандартного массива показано в таблице 5.5.

Таблица 5.5