Быстрая сортировка Хоара.
Данный алгоритм относится к распределительным и обеспечивает показатели эффективности 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
Дата добавления: 2016-07-22; просмотров: 1640;