Обменная сортировка с разделением (сортировка Хоара)

Сортировка методом простого обмена (методом "пузырька") является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы.

Можно существенно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением.

Алгоритм принадлежит Хоару (Charles Antony Richard Hoare), который опубликовал и тщательно проанализировал его в 1962 году.

Суть алгоритма основана на обмене элементов с разделением, поэтому иногда его называют обменной сортировкой с разделением. Поскольку производительность этого метода впечатляюща, автор назвал его "быстрой сортировкой".

Выберем случайным образом какой-то элемент массива, обозначим его y и будем называть его опорным элементом. Проблема выбора опорного элемента будет рассмотрена отдельно.

Наша задача разделить массив на две части – левую, с элементами меньшими y и правую с элементами большими y. Будем просматривать массив с двух сторон. Двигаясь слева направо, найдем элемент x[i]>y, а, двигаясь справа налево, найдем элемент x[j]<y. Поменяем их местами и продолжим просмотр до тех пор, пока не встретимся в каком-то месте массива (j>j). Понятно, что после такого прохода массив будет разделен по принципу: слева стоят все элементы меньшие опорного, а справа – все элементы большие или равные.

Теперь тот же метод применим к левой и правой части, до тех пор, пока каждая часть не будет содержать только один элемент.

Пример разделения 1 (по Кормену):

в качестве опорного элемента выбран y=x[1]=5:

5 3 2 6 4 1 3 7

3 3 2 6 4 1 5 7

3 3 2 1 4 6 5 7

Пример разделения 2 (по Вирту):

в качестве опорного элемента выбран средний элемент y=42:

44 55 12 42 94 06 18 67

18 55 12 42 94 06 44 67

18 06 12 42 94 55 44 67

Пример разделения 3 (по Кнуту-Седгевику):

в качестве опорного элемента выбран первый элемент y=50, просмотр начинается со 2 элемента, затем происходит обмен j элемента с 1:

50 8 51 98 42 15 67 73

50 8 15 98 42 51 67 73

50 8 15 42 98 51 67 73

48 8 15 50 98 51 67 73

{Partition по Вирту}

i:=1; j:=n;

выбор опорного элемента y;

repeat

while x[i]<y do i:=i + 1;

while x[j]>y do j:=j - 1;

if i<=j then begin z:=x[i]; x[i]:=x[j]; x[j]:=z

i:=i+1; j:=j-1 end;

until i>j;

Заметим, что при сравнении while x[i]<y (while x[j]>y), ищется элемент не x[i]>y а x[i]>=y (соответственно справа не <, а <=), то есть y действует как барьерный элемент.

В рассмотренном примере 1 разделения массива, после завершения разделения значения индексов равны: i=6, j = 5. Заметим, что условие if i<=j then предшествующее обмену необходимо – без него мы ошибочно бы обменяли местами 4 и 6.

В рассмотренном примере 2 разделения массива, после завершения разделения значения индексов равны: i=5, j = 3.

Все элементы разделились по принципу:

x[k]<=y, k=1,…i-1;

x[k]>=y, k=j+1,n,

x[k]=y, k=j+1,…i-1.

Рассмотрим теперь разделение массива:

2 3 7 1 6 5 4

1 3 7 2 6 5 4

После завершения разделения значения индексов равны: i=2, j = 1. Здесь выбор среднего элемента в качестве опорного является неудачным, так как после деления имеем разбиение на левую часть из 1 элемента и правую часть из (n-1) элемента.

С тем же успехом, можно выбирать в качестве опорного первый или последний элементы массива, которые тоже дадут плохой вариант для предварительно отсортированных массивов.

1 2 3 4 5 6 7

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

Понятно, что лучшим опорным элементом для массива является медиана, то есть значение, которое разобьет массив на две равные части. Однако поиск медианы может вызвать трудо- и времязатраты, сопоставимые с сортировкой массива.

Хоар предложил два способа улучшить выбор опорного элемента y:

• выбирать случайным образом элемент массива,

• искать медиану трех случайно взятых элементов массива (средний по величине).

Ахо предлагает выбирать у как наибольшее значение из двух первых элементов массива.

Запишем теперь общий алгоритм, рекурсивно вызывая процедуру сортировки:

Procedure Quicksort(var x:vector);

Procedure sort(l,r: integer);

Var i, j: integer;

y, z: integer;

Begin

i:=l; j:=r;

y:=x[(l+r) div 2];

repeat

while x[i]<y do i:=i + 1;

while x[j]>y do j:=j - 1;

if i<=j then begin z:=x[i]; x[i]:=x[j]; x[j]:=z

i:=i+1; j:=j-1 end;

until i>j;

if l < j then sort (l, j);

if i < r then sort(i, r)

end;

sort(1, n)

end; {quicksort}

Исключение рекурсии в этом алгоритме достигается использованием стека, в который запоминается запрос на сортировку одной из частей (для простоты - правой).

Procedure Quicksort(var x:vector);

Var i, j, l, r: integer;

y, z: integer;

S: stack;

Begin

Push(s,1,n);

Repeat

R:=pop(S);

L:=pop(S);

repeat

i:=l; j:=r;

y:=x[(l+r) div 2];

repeat

while x[i]<y do i:=i + 1;

while x[j]>y do j:=j - 1;

if i<=j then

begin

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

i:=i+1; j:=j-1

end;

until i>j;

if i < r then Push(S,i, r)

r:= j;

until l>=r;

until Empty(S);

end; {quicksort}

В стеке было бы рациональнее хранить адрес самой длинной части и продолжать разбиение коротких частей. Этого легко добиться с помощью условия:

If j-l < r-i then

begin

if i < r then Push(S,i, r);

r:= j;

end

else

begin

if l < j then Push(S,l, j)

l:= i;

end;

Еще один способ улучшения метода, заключается в использовании простых методов для разделенных подмассивов малой длины N. Например, при N = 9, рекомендуется использовать сортировку простой вставкой.

Алгоритм является самым полезным алгоритмом внутренней сортировки, так как требует мало памяти и опережает другие алгоритмы по среднему времени выполнения.

Характеристики алгоритма «быстрой сортировки» зависят от удачного выбора элемента Y для разбиения.

В хорошем случае число сравнений C= N*log(N), M=(N/6)*log(N).

Таким образом, быстрая сортировка эффективна лишь в среднем - время работы пропорционально N*log(N), в худшем случае она может работать очень медленно, ее N2.

Быстрая сортировка не является устойчивой, в отличии, например, от простых вставок, слияния списков, простого выбора.