2014-02-09
1469
Основной шаг алгоритма – процедура Partition, которая переставляет элементы массива А [ р..r ]нужным образом:
Листинг 2.7 – Процедура разбиения массива
Работа процедуры Partition показана на рис. 2.5. Элемент х = А [ p ]выбирается в качестве «граничного»; массив A [ p..q ]будет содержать элементы, не большие х, а массив A [ q + 1.. r ] – элементы, не меньшие х. Идея состоит в том, чтобы накапливать элементы, не большие х, в начальном отрезке массива (А [ р.. i ]), а элементы, не меньшие х – в конце (A [ j.. r ]). В начале оба «накопителя» пусты: i = р – 1, j = r + 1.
Внутри цикла while (в строках 5-8) к начальному и конечному участкам присоединяются элементы (как минимум по одному). После выполнения этих строк А [ i ] ≥ х ≥ A [ j ]. Если поменять А [ i ]и A [ j ]местами, то их можно будет присоединить к начальному и конечному участкам.
В момент выхода из цикла выполнено неравенство i ≥ j. При этом массив разбит на части А [ р ],..., A [ j ]и A [ j + 1],..., А [ r ]; любой элемент первой части не превосходит любого элемента второй части. Процедура возвращает значение j.
|
|
|
Хотя идея процедуры очень проста, сам алгоритм содержит ряд тонких моментов. Например, не очевидно, что индексы i и j не выходят за границы промежутка от р до r в процессе работы. Другой пример: важно, что в качестве граничного значения выбирается А [ р ], а не, скажем, А [ r ]. В последнем случае может оказаться, что А [ r ]– самый большой элемент массива, и в конце выполнения процедуры будет i = j = r, так что возвращать q = j будет нельзя – нарушится требование q < r, и процедура Quicksort зациклится.
Время работы процедуры Partition составляет Q(n), где п = r – р + 1.
Рисунок 2.5 – Работа процедуры Partition
Незакрашенные элементы относятся к уже сформированным фрагментам, закрашенные ещё не распределены. (а) Начальное состояние массива, начальный и конечный куски пусты. Элемент х = А [ р ]= 5 используется в качестве граничного. (б) Результат первого прохода цикла while (строки 4-8). (в) Элементы А [ i ]и A [ j ]меняются местами (строка 10). (г) Результат второго прохода цикла while. (д) Результат третьего (последнего) прохода цикла while. Поскольку i ≥ j, процедура останавливается и возвращает значение q = j. Элементы слева от A [ j ](включая сам этот элемент) не больше, чем х = 5, а элементы справа от A [ j ]не меньше, чем х = 5.
function FindMedium(L, R: integer): integer;
{Нахождение индекса "среднего" элемента}
var
MedIndex, {индекс "среднего" элемента}
Left, Right, Median: integer;
begin
Left:= A[L]; Right:= A[R]; Median:= A[(L+R) div 2];
{Берем два крайних элемента и один из середины массива}
if (Left = Median) and (Median = Right) then begin
{Если все три элемента одинаковы, то ищем неравный им}
i:= L;
while (A[i] = Median) and (i < R) do i:= i + 1;
{Если найден неравный элемент, то берем его третьим}
|
|
|
if A[i] <> Median then Median:= A[i];
end;
if (Left = Median) and (Median = Right) then begin
{Все элементы массива одинаковы и "средний" не найден}
FindMedium:= 0;
end else begin
{Выбираем "средний" из трех разных элементов}
if Left <= Median then
if Median <= Right then
MedIndex:= (L+R) div 2
else
if Left <= Right then MedIndex:= R
else MedIndex:= L
else
if Left >= Right then
MedIndex:= (L+R) div 2
else
if Left >= Right then
MedIndex:= R
else
MedIndex:= L;
FindMedium:= MedIndex;
end;
end; {FindMedium}
Листинг 2.8 – Функция нахождения разделяющего элемента быстрой сортировки
procedure QuickSort(L, R: integer);
var
MedItem, {значение "среднего" элемента}
MedIndex, {индекс "среднего" элемента}
Tmp, i, j: integer; {вспомогательные переменные}
begin
MedIndex:= FindMedium(L, R);
if MedIndex <> 0 then begin
{Сортируем, если найден "средний" элемент}
MedItem:= A[MedIndex];
{Разбиваем массив на две части}
i:= L; j:= R;
while i <= j do begin
{Ищем первый слева элемент, больший, чем MedItem}
while A[i] < MedItem do i:= i + 1;
{Ищем первый справа элемент, меньший, чем MedItem}
while A[j] > MedItem do j:= j - 1;
if i <= j then begin {Меняем местами найденные элементы}
Tmp:= A[i];
A[i]:= A[j];
A[j]:= Tmp;
i:= i + 1;
j:= j - 1;
end;
end;
{Сортируем две части массива по отдельности}
if L < j then QuickSort(L, j);
if i < R then QuickSort(i, R);
end;
end; {QuickSort}
begin {HoarSort}
QuickSort(1, n);
end; {HoarSort}
Листинг 2.9 – Быстрая сортировка
