2.5.3 Разбиение массива

Основной шаг алгоритма – процедура 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 составляет (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 – Быстрая сортировка