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

Сортировка трех выбранных элементов выполняется на основе одного малоизвестного и малоиспользуемого метода. Предположим, что выбраны элементы a, b и c. Сравниваем а и b. Если b меньше чем я, поменять их местами. Таким образом, получим a < b. Сравниваем a и c. Если c меньше чем a, поменять их местами. Получим a < c. После выполнения этих сравнений нам будет известно, что элемент a содержит минимальное значение из трех выбранных элементов, поскольку оно меньше или равно значениям элементов b и c. Сравниваем b и с. Если с меньше чем b, поменять их местами. Теперь элементы расположены в порядке a< b

Это улучшение, несмотря на кажущуюся медлительность, на практике работает быстрее, чем стандартная быстрая сортировка. Надо признать, увеличение скорости незначительно, но, тем не менее, ощутимо.

Теперь оставим в покое алгоритм выбора базового элемента и перейдем к рассмотрению улучшений, касающихся других аспектов быстрой сортировки. Быстрая сортировка - это рекурсивный алгоритм, и уже было показано, каким образом легко избавиться от одного из рекурсивных вызовов. Исключение второго рекурсивного вызова потребует больших усилий, но это может быть оправдано, поскольку позволит устранить некоторые вызовы, установку стека и т.п.

Рассмотрим рекурсивный вызов. Задаются четыре параметра, два из которых постоянны, а два других от вызова к вызову могут изменяться. Постоянные параметры - aList и aCompare, переменные параметры - aFirst и aSecond. Рекурсивный вызов можно устранить за счет использования явного стека, который предназначен для заталкивания и выталкивания переменных параметров. При этом цикл будет выполняться до тех пор, пока стек не будет пустым.

Листинг 5.17. Быстрая сортировка со случайным выбором базового элемента

procedure QSNR(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

Stack : array [0..63] of integer;

{позволяет разместить до 2 миллиардов элементов}

SP : integer;

begin

{инициализировать стек}

Stack[0] := aFirst;

Stack[1] := aLast;

SP := 2;

while (SP <> 0) do

begin

{вытолкнуть верхний подфайл}

dec(SP, 2);

aFirst := Stack[SP];

aLast := Stack[SP+1];

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

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(L);

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 (R - aFirst) < (aLast - R) then begin

Stack [SP] :=succ(R);

Stack[SP+1] := aLast;

inc(SP, 2);

aLast := R;

end

else begin

Stack[SP] := aFirst;

Stack [SP+1] :=R;

inc(SP, 2);

aFirst := succ(R);

end;

end;

end;

end;

procedure TDQuickSortNoRecurse( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

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

QSNR(aList, aFirst, aLast, aCompare);

end;

И в этом листинге код состоит из двух процедур: процедуры-драйвера и процедуры собственно сортировки. Таким образом, общая схема работы алгоритма осталась неизменной, но в этом случае внутренняя процедура, QSNR, вызывается только один раз.

В процедуре QSNR объявляется стек Stack для хранения 64 элементов типа longint и указатель на стек SP, который будет указывать на начало стека. Комментарий жизнерадостно утверждает, что размера стека будет достаточно для хранения 2 миллиардов элементов. Через несколько минут мы докажем справедливость комментария. В начале процедуры в стек записываются переданные процедуре начальный и конечный индексы. Предполагается, что на индекс первого элемента указывает указатель стека, а индекс последнего элемента хранится в позиции SP+1. После записи индексов указатель стека перемещается на 2 позиции. (В реализации алгоритма может использоваться два стека: один для индексов aFirst, а второй - для индексов aLast. При этом для обоих стеков будет нужен только один указатель.)

Далее начинается выполнение цикла while, которое завершается, когда стек опустеет, что эквивалентно равенству SP=0.

В цикле из стека выталкиваются переменные aFirst и aLast и значение указателя стека уменьшается на 2. После этого мы входим в цикл, который присутствует и в стандартной быстрой сортировке. Он повторяется до тех пор, пока значение индекса aFirst не превысит значение индекса aLast. Заключительные операторы в цикле, где ранее находился рекурсивный вызов процедуры сортировки, представляют собой интересный блок кода. К этому моменту времени базовый элемент находится на своем месте, и подсписок успешно разбит на две части. Определяем, какая из частей длиннее и записываем ее в стек (т.е. заталкиваем в стек значения индексов его первого и последнего элемента) и переходим к меньшей части.

Давайте на минутку задумаемся, что происходит. Если нам несказанно повезло, и для каждого подсписка в качестве базового элемента были выбраны их действительные медианы, то размеры подсписков будут составлять ровно половину размера подсписка более высокого уровня. Если в исходном списке было, например, 32 элемента, он будет разбит на 2 подсписка по 16 элементов, каждый из которых, в свою очередь, будет разбит еще на два подсписка по 8 элементов и т.д. Таким образом, максимальная глубина вложения подсписков в стеке будет равна пяти, поскольку 2(^5^)=32. Подумайте над этим. Мы затолкнем в стек подсписок из 16 элементов, разобьем второй такой же список на два списка по 8 элементов, затолкнем в стек один из списков длиной 8 элементов, а второй разобьем на два подсписка по 4 элемента и т.д. Пока мы дойдем до подсписка с одним элементом, в стеке уже будут находиться подсписок из 16 элементов, подсписок из 8 элементов, подсписок из 4 элементов, подсписок из 2 элементов и подсписок из 1 элемента. Пять уровней. Таким образом, для сортировки списка, содержащего 2 миллиарда элементов, будет достаточно 32 уровней (как это указано в комментарии к процедуре QSNR), если, конечно, каждый раз мы будем удачно выбирать базовый элемент.

Однако приведенное выше доказательство справедливо только в том случае, если нам очень повезет, не правда ли? На самом деле, нет. Если каждый раз в стек помещать больший подсписок, а продолжать работать с меньшим, то глубину вложения подсписков будет определять именно меньший подсписок. Поскольку размер меньшего подсписка будет всегда меньше или равен половине разбиваемого списка, результирующая глубина стека не будет превышать глубину стека для описанного выше случая удачного выбора базового элемента. Таким образом, размера объявленного в процедуре стека окажется вполне достаточно.

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

Таким образом, нам удалось избавиться от рекурсии, но, как ни странно, экономия времени оказалась незначительной. Более того, в некоторых случаях последний алгоритм работает даже медленнее стандартного (можно предположить, что снижение скорости вызвано определением меньшего списка из двух). Известны и другие улучшения, но они также не дают значительного выигрыша в скорости.

Может быть, у некоторых читателей после изучения кода, приведенного в листинге 5.16, возникла идея написания кода, который бы выполнялся в случае, когда в подсписке находится менее трех элементов. Это и будет нашей следующей областью внесения изменений в алгоритм быстрой сортировки.

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

Представьте себе, что разбиваются только подсписки размером не менее определенного количества элементов. К чему бы привел такой алгоритм быстрой сортировки? Мы получим грубо отсортированный список, т.е. все его элементы будут находиться вблизи требуемых позиций. Подсписки, которые были получены перед прекращением процесса разбиения, будут отсортированы в том смысле, что если подсписок X находится перед подсписком Y, то все элементы подсписка X будут расположены в отсортированном списке перед элементами подсписка Y. Это как раз самое удобное распределение для сортировки методом вставок. Таким образом, работу, начатую быстрой сортировкой, можно завершить с помощью сортировки методом вставок.

Это будет последнее улучшение быстрой сортировки, которое мы рассмотрим. Мы реализовали сверхоптимизированную сортировку без рекурсии, с использованием выбора базовой точки по медиане трех и сортировки методом вставок с целью завершения сортировки.

Листинг 5.18. Оптимизированная быстрая сортировка

const

QSCutOff = 15;

procedure QSInsertionSort(aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

IndexOfMin : integer;

Temp : pointer;

begin

{найти элемент с наименьшим значением из первых QSCutOff элементов и переместить его на первую позицию}

IndexOfMin := aFirst;

j := QSCutOff;

if (j > aLast) then

j := aLast;

for i := succ(aFirst) to j do

if (aCompare(aList.List^[i], aList.List^[IndexOfMin]) < 0) then

IndexOfMin := i;

if (aFirst <> indexOfMin) then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[IndexOfMin];

aList.List^[IndexOfMin] := Temp;

end;

{выполнить сортировку методом вставок}

for i := aFirst+2 to aLast do

begin

Temp := aList.List^[i];

j := i

while (aCompare(Temp, aList.List^[j-1]) < 0) do

begin

aList.List^[j] := aList.List^[j-1];

dec(j);

end;

aList.List^ [j ] :=Temp;

end;

end;

procedure QS( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdComparSFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

Stack : array [0..63] of integer;

{позволяет разместить до 2 миллиардов элементов}

SP : integer;

begin

{инициализировать стек}

Stack[0] := aFirst;

Stack[1] := aLast;

SP := 2;

{пока в стеке есть подфайлы}

while (SP<> 0) do

begin

{вытолкать верхний подфайл}

dec(SP, 2);

aFirst := Stack[SP];

aLast := Stack[SP+1];

{повторять пока в подфайле есть достаточное количество элементов}

while ((aLast - aFirst) > QSCutOff) do

begin

{выполнить сортировку первого, среднего и последнего элементов и в качестве базовой точки выбрать средний - метод медианы трех}

R := (aFirst + aLast) div 2;

if aCompare(aList.List^[aFirst], aList.List^[R]) > Othen begin

Temp := aList.List^[aFirst];

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

aList.List^[R] := Temp;

end;

if aCompare(aList.List^[aFirst], aList.List^[aLast]) > 0 then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[aLast];

aList.List^ [aLast] := Temp;

end;

if aCompare(aList.List^[R], aList.List^[aLast]) > 0 then begin

Temp := aList.List^[R];

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

aList.List^ [aLast] :=Temp;

end;

Pivot := aList.List^[R];

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

L := aFirst;

R := 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 (R - aFirst) < (aLast - R) then begin

Stack[SP] :=succ(R);

Stack[SP+1] := aLast;

inc(SP, 2);

aLast := R;

end

else begin

Stack[SP] := aFirst;

Stack [SP+1] :=R;

inc(SPs 2);

aFirst := succ(R);

end;

end;

end;

end;

procedure TDQuickSort( aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

begin

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

QS(aList, aFirst, aLast, aCompare);

QSInsertionSort(aList, aFirst, aLast, aCompare);

end;

Эта оптимизированная быстрая сортировка состоит из трех процедур. Первая из них - вызываемая процедура TDQuickSort. Она проверяет корректность переданных параметров, для частично сортировки списка вызывает процедуру QS, а затем для окончательной сортировки вызывает процедуру QSInsertionSort. Процедура QS выполняет нерекурсивный процесс разбиения списка до получения подсписков определенного минимального размера. QSInsertionSort представляет собой процедуру оптимизированной сортировки методом вставок для частично отсортированного списка. В частности, обратите внимание, что элемент с наименьшим значением находится в первых QSCutOf f элементах списка. Это вызвано выполнением процесса разбиения и тем фактом, что при достижении размеров подсписков QSCutOff элементов разбиение прекращается.

Стоила ли игра свеч? Тесты однозначно показывают, что стоила. При сортировке 100000 элементов типа longint оптимизированный алгоритм сортировки потребовал на 18% меньше времени, чем стандартный.