Быстрая сортировка хоара.

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

Данный алгоритм относится к распределительным и обеспечивает показатели эффективности 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 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, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.