Быстрая сортировка Хоара

Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении.

Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и производится следующее сравнение. Если ключи не удовлетворяют критерию, то записи R[i] и R[j] меняются местами. При этом индекс j фиксируется и начинает меняться индекс i(увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает изменяться j и т.д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящаяся на позиции встречи индексов, стоит на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - большие. Тот же самый алгоритм применяется к левому подмножеству, а затем к правому. Записи подмножества распределяются по двум еще меньшим подмножествам и т.д., и т.д. Распределение заканчивается, когда полученное подмножество будет состоять из единственного элемента - такое подмножество уже является упорядоченным.

Процедура сортировки в примере 3.16 рекурсивная. При ее вызове должны быть заданы значения границ сортируемого участка от 1 до N.

{===== Программный пример 3.16 =====}

{ Быстрая сортировка Хоара }

Procedure Sort(var a: Seq; i0,j0: integer);

{ i0, j0 - границы сортируемого участка }

Var i, j: integer; { текущие индексы в массиве }

flag: boolean; { признак меняющегося индекса: если

flag=true - уменьшается j, иначе - увеличивается i }

x: integer;

begin

if j0 <= i0 Exit; { подмножество пустое или из 1 эл-та }

i:=i0; j:=j0;

flag:=true; { вначале будет изменяться j }

while i < j do begin

if a[i] > a[j] then begin

x:=a[i]; a[i]:=a[j]; a[j]:=x; { перестановка }

{ после перестановки меняется изменяемый индекс }

flag:= not flag;

end;

{ реально изменяется только один индекс }

if flag then j:=j-1 else i:=i+1;

end;

Sort(a,i0,i-1); { сортировка левого подмассива }

Sort(a,i+1,j0); { сортировка правого подмассива }

end;

Результаты трассировки примера приведены в таблице 3.10. В каждой строке таблицы показаны текущие положения индексов i и j, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.

Таблица 3.10