Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Во многих книгах в качестве базового элемента выбирается первый или последний элемент списка. Если в исходном списке элементы располагались в произвольном порядке, стратегия выбора первого или последнего элемента ничем не отличается от любой другой. Но если исходный список был отсортирован в прямом или обратном порядке, выбор в качестве базового элемента первого или последнего элемента списка приводит нас к наихудшему случаю для алгоритма быстрой сортировки. Следовательно, первый или последний элемент нежелательно выбирать в качестве базового. Никогда так не делайте.

Намного лучше в качестве базового элемента брать средний элемент исходного списка. Остается только надеяться, что он будет находиться вблизи среднего элемента списка. В списке, элементы которого не упорядочены, выбор базового элемента не имеет значения, но если список уже отсортирован в прямом или обратном порядке, средний элемент будет лучшим выбором.

После выбора базового элемента можно перейти к описанию алгоритма разбиения списка. Добро пожаловать в известные своей быстротой внутренние циклы быстрой сортировки! Мы будем оперировать с двумя индексами: первый будет использоваться для прохождения по элементам списка слева направо, а второй -справа налево. Начинаем справа, и идем к левому краю списка, сравнивая значение каждого элемента со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого меньше или равно значению базового элемента. Это был внутренний цикл 1: сравнение двух элементов и уменьшение значения индекса. Затем та же операция выполняется слева. Проход выполняется в направлении к правому концу списка. Значение каждого элемента сравнивается со значением базового элемента. Цикл завершается, если найден элемент, значение которого больше или равно значению базового элемента. Это внутренний цикл 2: сравнение двух элементов и увеличение значения индекса.

На этом этапе могут возникнуть две ситуации. Первая - левый индекс меньше правого. Это говорит о том, что два элемента, на которые указывают индексы, расположены в списке в неверном порядке (т.е. значение элемента слева больше значения базового элемента, а значение элемента справа меньше значения базового элемента). Меняем элементы местами и продолжаем выполнение внутренних циклов. Вторая ситуация - индексы равны (т.е. значение левого индекса равно значению правого индекса) или индексы пересеклись (т.е. значение левого индекса больше значения правого индекса). В таком случае выполнение циклов можно завершить: список был успешно разделен.

Листинг 5.14. Стандартная быстрая сортировка

procedure QSS( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

begin

{пока в списке есть хотя бы два элемента}

while (aFirst < aLast) do

begin

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

Pivot := aList.List^[(aFirst+aLast) div 2];

{задать начальные значения индексов и приступить к разбиению списка}

L := pred(aFirst);

R := succ(aLast);

while true do

begin

repeat

dec(R);

until (aCompare (aList.List^ [R], Pivot) <=0);

repeat

inc(1);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >= R) then

Break;

Temp := aList.List^[L];

aList.List^[L] := aList.List^[R];

aList.List^[R] :=Temp;

end;

{выполнить быструю сортировку первого подфайла}

if (aFirst < R) then

QSS(aList, aFirst, R, aCompare);

{выполнить быструю сортировку второго подфайла - устранение рекурсии}

aFirst :=succ(R);

end;

end;

procedure TDQuickSortStd(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortStd');

QSS(aList, aFirst, aLast, aCompare);

end;

Поскольку алгоритм рекурсивный, быстрая сортировка в приведенной реализации разбита на две процедуры, как это имело место в случае сортировки слиянием. Первая процедура, TDQuickSortStd, - это процедура-драйвер. Она проверяет корректность задания входных параметров и вызывает вторую процедуру - QSS.

Именно она является рекурсивной, и именно она - суть всей реализации. Первое, что необходимо отметить, - процедура QSS работает только в том случае, когда в сортируемом списке есть хотя бы два элемента. В качестве базового элемента выбирается средний элемент списка. Затем устанавливаются начальные значения для индексов L и R - перед первым элементом и после последнего элемента списка соответственно. После этого в процедуре организован бесконечный цикл - при необходимости мы сами выйдем из него с помощью оператора break. Обратите внимание, что внутренние циклы организованы с помощью операторов Repeat..until. В первом цикле уменьшается значение индекса R до тех пор, пока он не будет указывать на элемент, значение которого меньше или равно значению базового элемента. Во втором цикле значение индекса L увеличивается до тех пор, пока он не будет указывать на элемент, значение которого больше или равно значению базового элемента. Затем сравниваются значения индексов L и R. Если значение L больше или равно значению R, индексы встретились или пересеклись, и мы выходим из бесконечного цикла. В противном случае два элемента, на которые указывают индексы, меняются местами, и выполнение цикла продолжается.