Сортировка методом Хоара
Ч. Хоар изобрел алгоритм сортировки массива и назвал его метод быстрой сортировки(Quicksort).
В Quicksort исходят из того соображения, что для достижения наилучшей Эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь нечто действительно поучительное.
Давайте, попытаемся воспользоваться
таким алгоритмом: выберем наугад
какой-либо элемент(назовем его x)
и будем просматривать слева наш массив
до тех пор, пока не обнаружим элемент
>x,
затем будем просматривать массив справа,
пока не встретим 
<x.
Теперь поменяем местами эти два элемента
и продолжим наш процесс просмотра и
обмена, пока оба просмотра не встретятся
где-то в середине массив. В результате
массив окажется разбитым на левую часть,
с ключами меньше(или равными) x,
и правую – с ключами больше(или равными)
x. Теперь этот процесс
представим в виде процедуры в программе
3.
Программа 3. Функция Partition
function Partition( var A : mas; l, r : Integer; x : integer ) : Integer;
var
i, j : Integer;
t : integer;
begin
i := l - 1;
j := r + 1;
repeat
repeat
j := j - 1;
until x >= A[j];
repeat
i := i + 1;
until A[i] >= x;
if i < j then
begin
t := A[i];
A[i] := A[j];
A[j] := t;
end;
until i >= j;
Partition := j;
end;
Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям, затем к частям частей, и так до тех пор, пока каждая их частей не будет состоять из одного-единственного элемента. Эти действия описываются программой 4.
Программа 4. Процедура RecoursiveQuicksort
procedure RecoursiveQuick( var A : mas; l, r : Integer );
var
m : Integer;
begin
if l < r then
begin
m := Partition(A, l, r, A[(l + r) div 2]);
RecoursiveQuick(A, l, m);
RecoursiveQuick(A, m + 1, r);
end;
end;
Сортировка методом Уильямса-Флойда
Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма "пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого "пирамидой". Алгоритм не требует дополнительной памяти. Высокая эффективность алгоритма и гарантированная надежность для самого "худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.
Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду "пирамиды". На втором этапе осуществляется сортировка "пирамиды".
Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:
X[1]
X[2] X[3]
X[4] X[5] X[6 ] X[7]
X[8] X[9] ................................
Структура дерева имеет логический характер - в памяти компьютера все элементы массива всеравно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка X[2i] и X[2i+1], где i - индекс данного элемента. Элементы массива, являющегося "пирамидой", обладают дополнительными свойствами:
1. Любой элемент пирамиды X[i] не меньше, чем его элементы-потомки X[2i] и X[2i+1] (соответственно первый элемент обладает максимальным значением):
X[i] >= X[2i],
X[i] >= X[2i+1]
2. Любая подпоследовательность элементов вида X[n\2+1], X[n\2+2], ... X[n] также является пирамидой, обладающей свойствами 1 и 2. После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.
В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвост а". Наибольший элемент массива окажется последним. "Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент X[1] и его потомки - X[2] и X[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент X[1] и наибольший из потомков: max(X[2], X[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом. Реализация этого алгоритма в программе 5.
Программа 5. Процедура PiramidaSort
Procedure PiramidaSort(var A: mas);
Var t, k, i, Y: Integer;
Begin
For i := 2 to N do { создание структуры бинарного дерева-"пирамиды" }
begin
t := i;
while t <> 1 do
begin k := t div 2;
If A[k] >= A[t] then t := 1
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k;
end
end
end;
For i := N-1 downto 1 do { сортировка массива-"пирамиды" }
begin
Y:=A[i+1]; A[i+1]:=A[1]; A[1]:=Y;
t := 1;
While t <> 0 do
begin
k := t+t;
If k > i then t := 0
else
begin
If k < i then If A[k+1] > A[k] then k := k+1;
If A[t] >= A[k] then t := 0
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k
end;
end;
end;
end;
End;