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

Процедура сортировки с использованием пирамиды требует выполнения порядка 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

Пример быстрой сортировки

Алгоритм недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

{ БЫСТРАЯ СОРТИРОВКА }

PROCEDURE sort (l, r: byte);

VAR

i, j: BYTE;

x, t: INTEGER;

BEGIN

i: = l; j: = r;

x: = b[(l + r) DIV 2];

REPEAT

WHILE b[i] < x DO i: = i + 1;

WHILE b[j] > x DO j: = j – 1;

IF i <= j THEN BEGIN

t: = b[i]; b[i]:=b[j]; b[j]:=t;

i: = i + 1; j: = j – 1

END;

UNTIL i > j;

IF l < j THEN sort (l, j);

IF r > i THEN sort (i, r)

END;

……...

BEGIN

…….

WRITELN ('быстрая сортировка');

sort (1, n 1);

………

END.

Анализ Quicksort. Для исследования производительности Quicksort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение х, мы затем проходим целиком по всему массиву. Следовательно, при этом выполняется точно п сравнений. Число же обменов можно определить из следующих вероятностных соображений. При заданной границе значений х ожидаемое число операций обмена равно числу элементов в левой части разделяемой, последовательности, т.е. n – 1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, если этот элемент перед этим находился в правой части. Вероятность этого равна (n – (х – 1))/ n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ х.

Представим себе, что мы счастливчики и нам всегда удается выбрать в качестве границы медиану, в этом случае каждый процесс разделения расщепляет массив на две половины и для сорти ровки требуется всего log n проходов. В результате общее число сравнений равно n*log n, а общее число обменов- n *log (n)/6. Нельзя, конечно, ожидать, что мы каждый раз будем выбирать медиану. Вероятность этого составляет только 1/ n. Удивительный, однако, факт: средняя производительность Quicksort при случайном выборе границы отличается от упомянутого оптимального варианта лишь коэффици ентом 2* ln (2).

Как бы то ни было, но Quicksort присущи и некоторые недостатки. Главный из них - недостаточно высокая производительность при небольших n, впрочем этим грешат все усовершенствованные методы. Но перед другими усовершенствованными методами этот имеет то преимущество, что для обработки небольших частей в него можно легко включить какой-либо из прямых методов сортировки. Это особенно удобно делать в случае рекурсивной версии программы.

Остается все еще вопрос о самом плохом случае. Как тогда будет работать Quicksort? К несчастью, ответ на этот вопрос неутешителен и демонстрируе т одно неприятное свойс тво Quicksort. Разберем, ска жем, тот несчастный случай, когда каждый раз для сравнения выбирается наибольшее из всех значений в указанной части. Тогда на каждом этапе сегмент из n элементов будет расщепляться на левую часть, состоящую из n – 1 элементов, и правую, состоящую из одного-единственного элемента. В результате потребуется n (а не log n) разделений и наихудшая производительность метода будет порядка n ² .

Явно видно, что главное заключается в выборе элемента для сравнения - х. В нашей редакции им становится средний элемент. Заметим, однако, что почти с тем же успехом можно выбирать первый или последний. В этих случаях хуже всего будет, если массив окажется первоначально уже упорядочен, ведь Quicksort определенно «не любит» такую тривиальную работу и предпочитает иметь дело с неупорядоченными массивами. Выбирая средний элемент, мы как бы затушевываем эту странную особенность Quicksort, поскольку в этом случае первоначально упорядоченный массив будет уже оптимальным вариантом. Таким образом, фактически средняя производительность при выборе среднего элемента чуточку улучшается. Сам Хоар предполагает, что х надо выбирать случайно, а для небольших выборок, вроде всего трех ключей, останавливаться на медиане. Такой разумный выбор мало влияет на среднюю производительность Quicksort, но зато значительно ее улучшает (в наихудших случаях). В некотором смысле быстрая сортировка напоминает азартную игру: всегда следует учитывать, сколько можно проиграть в случае невезения.