Сортировка с помощью пирамиды

Процедура сортировки с использованием пирамиды требует выполнения порядка n*log n шагов (логарифм - двоичный) в худшем случае, что делает ее особо привлекательной для сортировки больших массивов.

{процедура просеивания Флойда in situ}

PROCEDURE sito (l, r: byte);

VAR

i, j: BYTE;

x: INTEGER;

BEGIN

i: = l; j: = 2*i; x: = a[i];

IF (j < r) AND (a[j + 1] < a[j]) THEN j: =j + 1;

WHILE (j < = r) AND (a[j] < x) DO BEGIN

a[i]: = a[j]; i: = j; j: = 2*j;

IF (j < r) AND (a[j + 1] < a[j]) THEN j: = j + 1;

END;

a[i]: = x

END;

….

BEGIN

….

{построение пирамиды}

l: = (n DIV 2) + 1;

WHILE l > 1 DO BEGIN

l: = l – 1; sito (l, n);

END;

….

{полная сортировка}

r: = n;

WHILE r > 1 DO BEGIN

x: = a[1]; a[1]: = a[r]; a[r]: = x;

r: = r – 1; sito (1, r);

END;

Анализ Heapsort. На первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. И действительно, процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для больших же n Heapsort очень эффективна; чем больше n, тем лучше она работает. Она даже становится сравнимой с сортировкой Шелла.

В худшем случае нужно n /2 сдвигающих шагов, они сдвигают элементы на log (n /2), log (n /2 – 1),......, log(n – l) позиций (логарифм (по основанию 2) «обрубается» до следующего меньшего целого). Следовательно, фаза сортировки требует n – 1 сдвигов с самое большое log(n – l), log (n –),..., 1 перемещениями. Кроме того, нужно еще n – 1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев Heapsort потребует n*log n шагов. Великолепная производительность в таких плохих случаях -одно из привлекательных свойств Heapsort.

Совсем не ясно, когда следует ожидать наихудшей (или наилучшей) производительности. Но вообще-то кажется, что Heapsort «любит» начальные последовательности, в которых элементы более или менее отсортированы в обратном порядке. Поэтому ее поведение несколько неестественно. Если мы имеем дело с обратным порядком, то фаза порождения пирамиды не требует каких-либо перемещений. Среднее число перемещений приблизительно равно n/2*log(n), причем отклонения от этого значения относительно невелики.

Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть «методом быстрой сортировки - Quicksort».

В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, если сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь и нечто действительно поучительное.

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследим этот процесс на примере нашего стандартного массива (таблица 5.7).

Таблица 5.7