Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 12 (всего у книги 36 страниц)
begin
aList.List^[j] := aList.List^[j-h];
dec(j, h);
end;
aList.List^[j ] := Teilend;
{уменьшить значение h на треть}
h := h div 3;
end;
end;
Математические зависимости для анализа быстродействия сортировки методом Шелла достаточно сложны. В общем случае для оценки времени выполнения сортировки при различных значениях h приходится ограничиваться статистическими данными. Тем не менее, анализ быстродействия алгоритма Шелла практически не имеет смысла, поскольку существуют более быстрые алгоритмы.
Что касается устойчивости, то при перестановке элементов, далеко отстоящих друг от друга, возможно нарушение порядка следования элементов с равными значениями. Следовательно, сортировка методом Шелла относится к группе неустойчивых алгоритмов.
Сортировка методом прочесывания
Этот раздел будет посвящен действительно странному алгоритму сортировки -сортировке методом прочесывания (comb sort). Он не относится к стандартным алгоритмам. На сегодняшний день он малоизвестен и поиск информации по нему может не дать никаких результатов. Тем не менее, он отличается достаточно высоким уровнем быстродействия и удобной реализацией. Метод был разработан Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box) и опубликован в журнале "Byte" в апреле 1991 года. Фактически он использует пузырьковую сортировку таким же образом, как сортировка методом Шелла использует сортировку методом вставок.
Перетасуйте карты и снова разложите их на столе. Выделите первую и девятую карту. Если они находятся в неправильном порядке, поменяйте их местами. Выделите вторую и десятую карты и, при необходимости, поменяйте их местами. То же самое проделайте для третьей и одиннадцатой карты, четвертой и двенадцатой, а затем пятой и тринадцатой. Далее сравнивайте и переставляйте пары карт (1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12) и (7, 13) (т.е. карты, отстоящие друг от друга на шесть позиций). А теперь выполните проход по колоде для карт, отстоящих друг от друга на четыре позиции, затем на три и две позиции. После этого выполните стандартную пузырьковую сортировку (которую можно рассматривать как продолжение предыдущего алгоритма для соседних карт).
Таким образом, вначале карты большими "прыжками" передвигаются в требуемую область. Как и сортировка методом Шелла, прочесывание неудобно выполнять на картах, но в функции для сортировки методом прочесывания требуется всего два цикла – один для уменьшения размера "прыжков", а второй – для выполнения разновидности пузырьковой сортировки.
Как были получены значения расстояний 8, 6, 4, 3, 2, 1? Разработчики этого метода сортировки провели большое количество экспериментов и эмпирическим путем пришли к выводу, что значение каждого последующего расстояния "прыжка" должно быть получено в результате деления предыдущего на 1.3. Этот "коэффициент уменьшения" был лучшим из рассмотренных и позволял сбалансировать зависимость времени выполнения от длины последовательности значений расстояний и времени выполнения пузырьковой сортировки.
Более того, создатели алгоритма пришли к необъяснимому выводу, что значения расстояний между сравниваемыми элементами 9 и 10 являются неоптимальными, т.е. если в последовательности расстояний присутствует значение 9 или 10, его лучше поменять на 11. В этом случае сортировка будет выполняться гораздо быстрее. Проведенные эксперименты подтверждают этот вывод. Теоретических исследований сортировки методом прочесывания на сегодняшний день не производилось, и поэтому нет определенного объяснения, почему приведенная последовательность расстояний является оптимальной.
Рисунок 5.7. Сортировка методом прочесывания (показаны только перестановки)
Листинг 5.10. Сортировка методом прочесывания
procedure TDCombSort(aList : TList;
aFirst : integer; aLast : integer;
aCompare : TtdCompareFunc);
var
i, j : integer;
Temp : pointer;
Done : boolean;
Gap : integer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDCombSort');
{начать с расстояния, равного количеству элементов}
Gap := succ(aLast – aFirst);
repeat
{предположить, что сортировка будет выполнена на этом проходе}
Done := true;
{calculate the new gap}
Gap := (longint(Gap) * 10) div 13;
{Gap := Trunc(Gap / 1.3);}
if (Gap < 1) then
Gap := 1
else
if (Gap = 9) or (Gap = 10) then
Gap := 11;
{упорядочить два элемента, отстоящих друг от друга на Gap элементов}
for i := aFirst to (aLast – Gap) do
begin
j := i + Gap;
if (aCompare(aList.List^[j], aList.List^[i]) < 0) then begin
{поменять местами элементы с индексами j и (j-Gap)}
Temp := aList.List^[j];
aList.List^[j] := aList.List^[i];
aList.List^[i] := Temp;
{была выполнена перестановка, следовательно, сортировка не завершена}
Done := false;
end;
end;
until Done and (Gap = 1);
end;
В экспериментах, проведенных автором книги, сортировка методом прочесывания была немного быстрее сортировки методом Шелла (на последовательности Кнута). Кроме того, ее легче запрограммировать (если не говорить о необходимости исключения расстояний 9 и 10). Очевидно, что сортировка методом прочесывания, как и методом Шелла, принадлежит к группе неустойчивых алгоритмов.
Самые быстрые алгоритмы сортировки
И вот, наконец, мы добрались до самых быстрых алгоритмов сортировки. Они очень широко используются на практике и очень важно понимать их особенности, что позволит оптимальным образом реализовывать их в различных приложениях.
Сортировка слиянием
Сортировка слиянием (merge sort) считается весьма интересным алгоритмом. Она привлекательна своей простотой и наличием некоторых важных особенностей (например, она принадлежит к алгоритмам класса O(n log(w)) и не имеет худших случаев), но если приступить к его реализации, можно натолкнуться на большую проблему. Тем не менее, сортировка слиянием очень широко используется при необходимости сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти.
Мы будет рассматривать сортировку слиянием по шагам, начиная со слияния. Затем мы опишем, как использовать алгоритм для выполнения сортировки. В качестве примера мы не будем пользоваться картами – алгоритм легко понять и без карт.
Представьте себе, что имеется два уже отсортированных списка и необходимо сформировать один список, объединяющий все элементы исходных списков. План А состоит в том, чтобы скопировать оба списка в результирующий и выполнить его сортировку. Но в этом случае, к сожалению, мы не пользуемся тем, что исходные списки уже отсортированы. План Б предусматривает слияние. Смотрим на первые элементы в обоих списках. Элемент с меньшим значением переносим в результирующий список. Снова смотрим на первые элементы в обоих списках и снова переносим в результирующий список элемент с меньшим значением, удаляя его из исходного списка. Описанный процесс продолжается до тех пор, пока не исчерпаются элементы одного из списков. После этого в результирующий список можно перенести все оставшиеся в исходном списке элементы. Такой алгоритм формально известен под названием алгоритма двухпутевого слияния (two-way merge algorithm ).
Конечно, на практике элементы не удаляются из исходных списков. Вместо удаления используются указатели на текущие начальные элементы списков, которые при копировании передвигаются на следующий элемент.
Листинг 5.11. Слияние двух отсортированных массивов TList
procedure TDListMerge( aList 1, aList2, aTarget List : TList;
aCompare : TtdCompareFunc);
var
Inx1, Inx2, Inx3 : integer;
begin
{подготовить результирующий список}
aTargetList.Clear;
aTargetList.Capacity := aList1.Count + aList2.Count;
{инициализировать счетчики}
Inx1 := 0;
Inx2 := 0;
Inx3 := 0;
{выполнять цикл до исчерпания элементов одного из списка...}
while (Inx1 < aList1.Count) and (Inx2 < aList2.Count) do
begin
{определить наименьшее значение из двух списков и скопировать его в результирующий список; увеличить значения индексов на единицу}
if aCompare (aList1.List^[Inx1], aList2.List^[Inx]) < = 0 then begin
aTargetList.List^[Inx3] := aList1.List^[Inx1];
inc(Inx1);
end
else begin
aTargetList.List^[Inx3] := aList2.List^[Inx2];
inc(Inx2);
end;
inc(Inx3);
end;
{выполнение цикла прекращается при исчерпании элементов одного из списков; если в первом списке еще остались элементы, скопировать их в результирующий список}
if (Inx1 < aList1.Count) then
Move(aList1.List^[Inx1], aTargetList.List^[Inx3],
(aList1.Count – Inx1) * sizeof(pointer)) {в противном случае скопировать все элементы, оставшиеся во втором списке, в результирующий список}
else
Move(aList2.List^[Inx2], aTargetList.List^[Inx3], (aList2.Count – Inx2) * sizeof(pointer));
end;
Обратите внимание, что в коде копирование оставшихся элементов в одном или другом списке выполняется с помощью процедуры Move. Для копирования можно было бы организовать небольшой цикл, однако процедура Move работает намного быстрее.
Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих исходных списках. Если в первом из них находится n элементов, а во втором – m, нетрудно прийти к выводу, что в худшем случае будет произведено (n + m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n).
Каким же образом алгоритм двухпутевого слияния помогает выполнить сортировку? Для его работы необходимо иметь два отсортированных списка меньшей длины, из которых создается один больший список. На основе такого описания можно прийти к рекурсивному определению сортировки слиянием: разделите исходный список на две половины, примените к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма слияния объедините подсписки в один отсортированный список. Рекурсия заканчивается, когда под-под-подсписок, переданный алгоритму сортировки, содержит всего один элемент, поскольку он, очевидно, является отсортированным.
Сортировка слиянием обладает только одним недостатком – алгоритм слияния требует наличия третьего списка, в котором будут храниться результаты слияния.
В отличие от всех ранее рассмотренных методов сортировки, которые сортируют элементы непосредственно в самом исходном списке, сортировка слиянием для работы требует большого дополнительного объема памяти. В качестве первого приближения в самой простой реализации может показаться, что для выполнения сортировки понадобиться новый вспомогательный список, размер которого равен сумме размеров двух исходных списков. Элементы из обоих списков будут помещаться во вспомогательный список, а затем после слияния – в основной список. Несмотря на то что можно разработать алгоритм, который выполняет операцию слияния, не требуя вспомогательного списка, на практике его выполнение занимает намного больше времени. Поэтому при необходимости применения сортировки слиянием нужно смириться с дополнительными требованиями в отношении памяти.
Сколько же памяти потребуется? Только что мы решили, что в худшем случае будет использоваться список, размер которого равен размеру исходного списка, но за счет небольшой хитрости можно снизить требования по дополнительной памяти до половины размера исходного списка.
Представьте себе, что мы находимся на самом верхнем уровне рекурсивного алгоритма. Только что мы выполнили сортировку двух половин исходного списка (будем считать, что первый отсортированный подсписок находится в первой половине списка, а второй – во второй половине), а теперь переходим к их слиянию. Вместо того чтобы выполнить слияние во вспомогательный список, равный по размеру исходному, скопируем первую половину списка в другой список, размер которого равен только половине исходного. Теперь у нас есть вспомогательный список, заполненный элементами из первой половины исходного списка, и исходный список, первая половина которого считается пустой, а вторая заполнена вторым подсписком элементов. При слиянии мы не перезапишем ни один из элементов второго подсписка, поскольку точно известно, что все содержимое вспомогательного списка может поместиться в свободную половину исходного списка.
Листинг 5.12. Стандартная сортировка слиянием
procedure MSS(aList : TList;
aFirst : integer;
aLast : integer;
aCoropare : TtdCompareFunc;
aTempList : PPointerList);
var
Mid : integer;
i, j : integer;
ToInx : integer;
FirstCount : integer;
begin
{вычислить среднюю точку}
Mid := (aFirst + aLast) div 2;
{выполнить рекурсивную сортировку слиянием первой и второй половин списка}
if (aFirst < Mid) then
MSS(aList, aFirst, Mid, aCompare, aTempList);
if (suce(Mid) < aLast) then
MSS(aList, succ(Mid), aLast, aCompare, aTempList);
{скопировать первую половину списка во вспомогательный список}
FirstCount := suce(Mid – aFirst);
Move(aList.List^[aFirst], aTempList^[0], FirstCount * sizeof(pointer));
{установить значения индексов: i – индекс для вспомогательного списка (т.е. первой половины списка), j – индекс для второй половины списка, ToInx – индекс в результирующем списке, куда будут копироваться отсортированные элементы}
i := 0;
j := suce (Mid);
ToInx := aFirst;
{выполнить слияние двух списков}
{повторять до тех пор, пока один из списков не опустеет}
while (i < FirstCount) and (j <= aLast) do
begin
{определить элемент с наименьшим значением из следующих элементов в обоих списках и скопировать его; увеличить значение соответствующего индекса}
if (aCompare(aTempList^[i], aList.List^[j]) <= 0) then begin
aList.List^[ToInx] := aTempList^[i];
inc( i );
end
else begin
aList.List^[ToInx] := aList.List^[j];
inc(j);
end;
{в объединенном списке есть еще один элемент}
inc(ToInx);
end;
{если в первом списке остались элементы, скопировать их}
if (i < FirstCount) then
Move(aTempList^[i], aList.List^[ToInx], (FirstCount – i) * sizeof(pointer));
{если во втором списке остались элементы, то они уже находятся в нужных позициях, значит, сортировка завершено; если второй список пуст, сортировка также завершена}
end;
procedure TDMergeSortStd(aList : TList;
aFirst : integer;
aLast : integer;
aCompare : TtdCompareFunc);
var
TempList : PPointerList;
ItemCount: integer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDMergeSortStd');
{если есть хотя бы два элемента для сортировки}
if (aFirst < aLast) then begin
{создать временный список указателей}
ItemCount := suce(aLast – aFirst);
GetMem(TempList, (suce(ItemCount) div 2) * sizeof(pointer));
try
MSS(aList, aFirst, aLast, aCompare, TempList);
finally
FreeMem(TempList, (suce(ItemCount) div 2) * sizeof(pointer));
end;
end;
end;
Если вы внимательно изучите код, приведенный в листинге 5.12, то обнаружите, что он содержит процедуру-драйвер, TDMergeSortStd, которая вызывается для выполнения сортировки списка, и отдельную вспомогательную процедуру, MSS, выполняющую рекурсивную сортировку. Прежде всего, процедура TDMergeSortStd проверяет попадание индекса в допустимые пределы и сам список, а затем – присутствуют ли в списке хотя бы два элемента, которые можно сортировать. После этого создается вспомогательный список указателей с размером, достаточным для хранения половины количества элементов исходного массива. Далее вызывается рекурсивная процедура MSS.
Процедура MSS рекурсивно вызывает сама себя для сортировки первой и второй половин переданной ей части массива. Затем она копирует первую половину во вспомогательный массив. Начиная с этого момента, код представляет собой стандартную реализацию сортировки слиянием, копируя две половины списка в исходный список. Если после выполнения цикла сравнения и копирования во вспомогательном массиве остались элементы, процедура MSS их просто копирует. Если же элементы остались во второй половине списка, их можно не копировать, как и в стандартной реализации метода слияния: они уже находятся на своих местах.
Вывод функции быстродействия сортировки слиянием достаточно сложен. Для простоты ее определения лучше принять, что в исходном списке находится 2(^х^) элементов. Предположим, что элементов 32. На первом уровне рекурсии процедура MSS будет вызываться один раз и на этапе слияния будет не более 32 сравнений. На втором уровне рекурсии процедура MSS будет вызываться два раза, причем количество сравнений при каждом вызове не будет превышать 16. Далее рассматриваем третий, четвертый и, наконец, пятый уровень рекурсии (когда будет выполняться сортировка всего двух элементов), на котором будет иметь место 16 вызовов процедуры по два сравнения в каждом. Таким образом, общее количество сравнений будет равно 5 * 32. Но причиной, по которой было получено пять уровней рекурсии, является то, что мы постоянно на каждом уровне постепенно делили список на две равные половины, а 2(^5^) = 32, что, естественно означает, что log(_2_)32 = 5. Следовательно, не утруждая себя переходом от рассмотренного нами частного случая к общему, можно сказать, что сортировка слиянием принадлежит к классу O(n log(n)) алгоритмов.
Что касается устойчивости, то поскольку элементы перемещаются только при выполнении процедуры слияния, устойчивость всей сортировки слиянием будет зависеть от устойчивости самого слияния двух половин списка. Обратите внимание, что если в обеих половинах имеются элементы с одинаковым значением, то оператор сравнения гарантирует, что первым в результирующий список попадет элемент из первой половины списка. Это означает, что операция слияния сохраняет относительный порядок элементов, и, следовательно, сортировка слиянием будет устойчивой.
Если отслеживать вызовы процедуры MSS в отладчике, то можно обратить внимание, что для небольших интервалов она вызывается очень часто. Например, если в списке содержится 32 элемента, то для списка из 32 элементов процедура MSS будет вызвана один раз, для списка из 16 элементов – дважды, четыре раза для 8 элементов, восемь раз для 4 элементов и шестнадцать раз для 2 элементов (список минимальной длины), т.е. всего 31 раз. Это очень много, особенно если учитывать, что большая часть вызовов (29) приходится для списков длиной восемь и менее элементов. Если бы исходный список содержал 1024 элемента, процедура MSS была бы вызвана 1023 раза, из которых 896 вызовов приходилось бы на долю списков длиной восемь и менее элементов. Просто ужасно! Фактически, для сортировки коротких списков было бы эффективнее использовать нерекурсивный алгоритм. Это позволило бы повысить скорость всей сортировки. Кроме того, применение более простой процедуры дало бы возможность для коротких диапазонов исключить копирование элементов между основным и вспомогательным списком. И одним из лучших методов для ускорения сортировки слиянием является сортировка методом вставок.
Листинг 5.13. Оптимизированная сортировка слиянием
const
MSCutOff = 16;
procedure MSInsertionSort(aList : TList;
aFirst : integer; aLast : integer;
aCompare : TtdCompareFunc);
var
i, j : integer;
IndexOfMin : integer;
Temp : pointer;
begin
{найти наименьший элемент в списке}
IndexOfMin := aFirst;
for i := succ(aFirst) to aLast 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 MS(aList : TList; aFirst : integer; aLast : integer;
aCompare : TtdCompareFunc;
aTempList : PPointerList);
var
Mid : integer;
is j : integer;
ToInx : integer;
FirstCount : integer;
begin
{вычислить среднюю точку}
Mid := (aFirst + aLast) div 2;
{выполнить сортировку первой половины списка с помощью сортировки слиянием или если количество элементов достаточно мало, при помощи сортировки методом вставок}
if (aFirst < Mid) then
if (Mid-aFirst) <= MSCutOff then
MSInsertionSort(aList, aFirst, Mid, aCompare) else
MS (aList, aFirst, Mid, aCompare, aTempList);
{аналогично выполнить сортировку второй половины}
if (suce(Mid) < aLast) then
if (aLast-succ(Mid) ) <= MSCutOf f then
MSInsertionSort(aList, succ(Mid), aLast, aCompare)
else
MS (aList, suce(Mid), aLast, aCompare, aTempList);
{скопировать первую половину списка во вспомогательный список}
FirstCount := suce (Mid – aFirst);
Move(aList.List^[aFirst], aTempList^[0], FirstCount*sizeof(pointer));
{установить значения индексов: i – индекс для вспомогательного списка (т.е. первой половины списка), j – индекс для второй половины списка, ToInx -индекс в результирующем списке, куда будут копироваться отсортированные элементы}
i := 0;
j := suce (Mid);
ToInx := aFirst;
{выполнить слияние двух списков}
{повторять до тех пор, пока один из списков не опустеет}
while (i < FirstCount) and (j <= aLast) do
begin
{определить элемент с наименьшим значением из следующих элементов в обоих списках и скопировать его; увеличить значение соответствующего индекса}
if ( aCompare( aTempList^[i], aList.List^[j] ) <= 0 ) then begin
aList.List^[ToInx] := aTempList^[i];
inc(i);
end
else begin
aList.List^[ToInx] := aList.List^[ j ];
inc(j);
end;
{в объединенном списке есть еще один элемент}
inc(ToInx);
end;
{если в первом списке остались элементы, скопировать их}
if (i < FirstCount) then
Move(aTempList^[i], aList.List^[ToInx], (FirstCount – i) * sizeof(pointer));
{если во втором списке остались элементы, то они уже находятся в нужных позициях, значит, сортировка завершена; если второй список пуст, сортировка также завершена}
end;
procedure TDMergeSort(aList : TList;
aFirst : integer;
aLast : integer;
aCompare : TtdCompareFunc);
var
TempList : PPointerList;
ItemCount: integer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDMergeSort');
{если есть хотя бы два элемента для сортировки}
if (aFirst < aLast) then begin
{создать временный список указателей}
ItemCount := suce (aLast – aFirst);
GetMem(TempList, (succ(ItemCount) div 2) * sizeof(pointer));
try
MS(aList, aFirst, aLast, aCompare, TempList);
finally
FreeMem(TempList, (succ(ItemCount) div 2) * sizeof(pointer));
end;
end;
end;
Несмотря на то что объем кода достаточно велик, в нем находятся всего три процедуры. Прежде всего, драйвер – TDMergeSort – процедура, которую мы вызываем. Как и в предыдущем случае, она используется для выделения из кучи памяти под вспомогательный список указателей и вызывает рекурсивную процедуру, названную в приведенном коде MS. В общих чертах процедура MS работает примерно так, как и ее предшественница – MSS (рекурсивная процедура для стандартной сортировки слиянием). Разница возникает только тогда, когда дело касается сортировки подсписков. Для небольших диапазонов элементов, длина которых меньше, чем значение MSCutOff, процедура MS вызывает третью процедуру, MSInsertionSort, которая сортирует элементы без рекурсивного вызова. Для длинных диапазонов элементов, естественно, происходит рекурсивный вызов процедуры MS. MSInsertionSort ничем не отличается от рассмотренной нами ранее процедуры TDInsertionSort, за исключением одного – она не проверяет корректность входных параметров (в проверке нет необходимости, поскольку все параметры были проверены в TDMergeSort).
Поскольку в приведенном коде для сортировки коротких диапазонов в списке используется сортировка методом вставок, которая сама по себе является устойчивой, можно сказать, что оптимизированная сортировка слиянием также принадлежит к группе устойчивых алгоритмов.
Несмотря на то что сортировка слиянием требует дополнительной памяти (объем которой пропорционален количеству элементов в исходном списке), она обладает некоторыми интересными свойствами. Первое из них – сортировка слиянием принадлежит к классу O(n log(n)). Второе – она устойчива. Еще два алгоритма со скоростью работы O(n log(n)) и дополнительными требованиями к памяти, которые будут рассмотрены в этой главе, являются неустойчивыми. Третье – для сортировки слиянием не имеет значения ни порядок элементов в исходном списке (будь то список, отсортированный в прямом порядке или обратном), ни повторения значений в списке. Другими словами, она не имеет худшего случая.
В конце этой главы мы рассмотрим случай, в котором сортировка слиянием просто необходима, – сортировка связного списка.
И, наконец, сортировка слиянием используется для сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти. В этой ситуации выполняется сортировка частей файлов, запись этих частей в отдельные файлы, а затем их слияние в один файл.
Быстрая сортировка
И последний алгоритм, который будет рассмотрен в этой главе – быстрая сортировка (quicksort). (В книге мы опишем еще одну сортировку "в памяти" – пирамидальную сортировку, но она требует дополнительных знаний структуры данных – бинарного дерева. По этой причине рассмотрение пирамидальной сортировки отложено до главы 9.)
Алгоритм быстрой сортировки был разработан К.A.Р. Хоаром (C.A.R. Hoare) в 1960 году. Этот алгоритм, наверное, еще более известен, чем пузырьковая сортировка. В настоящее время он является самым широко используемым в программировании методом сортировки, что вызвано его крайне положительными характеристиками: это алгоритм класса O(n log(n)) для общего случая, он требует лишь незначительного объема дополнительной памяти, работает с различными типами входных списков и достаточно удобен для реализации. Но, к сожалению, быстрая сортировка имеет и несколько нежелательных характеристик: при его реализации допускается очень много ошибок (простые ошибки в реализации могут остаться незамеченными и при выполнении могут потребовать дополнительного времени), быстродействие в худшем случае составляет O(n(^2^)) и к тому же она неустойчива.
Кроме того, быстрая сортировка наиболее изучена. Со времени выхода в свет первой статьи Хоара многие исследователи изучали быструю сортировку и сформировали значительную базу данных по теоретическому определению времени выполнения, подкрепленную эмпирическими данными. Было предложено немало улучшений базового алгоритма, позволяющих увеличить скорость работы. Некоторые из предложенных улучшений будет рассмотрены в этой главе. При таком богатстве литературных источников по алгоритму быстрой сортировки, если следовать всем рекомендациям, у вас не должно возникнуть проблем с реализацией. (В последней оптимизированной реализации алгоритма использовалось более шести различных справочных пособий по алгоритмам. Причем в одной из них была приведена "оптимизированная" быстрая сортировка, которая была написана так плохо, что при одних и тех же входных данных работала даже медленнее, чем стандартный метод TList.Sort.)
Быстрая сортировка встречается везде. Во всех версиях Delphi, за исключением версии 1, метод TList.Sort реализован на основе алгоритма быстрой сортировки. Метод TStringList.Sort во всех версиях Delphi реализован с помощью быстрой сортировки. В С++ функция qsort из стандартной библиотеки времени выполнения также реализована на базе быстрой сортировки.
Основной алгоритм быстрой сортировки, как и сортировку слиянием, можно отнести к классу "разделяй и властвуй". Он разбивает исходный список на два, а затем для выполнения сортировки рекурсивно вызывает сам себя для каждой части списка. Таким образом, особое внимание в быстрой сортировке нужно уделить процессу разделения. В разбитом списке происходит следующее: выбирается элемент, называемый базовым, относительно которого переставляются элементы в списке. Элементы, значения которых меньше, чем значение базового элемента, переносятся левее базового, а элементы, значения которых больше, чем значение базового элемента, переносятся правее базового. После этого можно сказать, что базовый элемент находится на своем месте в отсортированном списке. Затем выполняется рекурсивный вызов функции быстрой сортировки для левой и правой частей списка (относительно базового элемента). Рекурсивные вызовы прекращаются, когда список, переданный функции сортировки, будет содержать всего один элемент, а, следовательно, весь список оказывается отсортированным.
Таким образом, для выполнения быстрой сортировки необходимо знать два алгоритма более низкого уровня: как выбирать базовый элемент и как наиболее эффективно переставить элементы списка таким образом, чтобы получить два набора элементов: со значениями, меньшими, чем значение базового элемента, и со значениями, большими, чем значение базового элемента.
Начнем с описания алгоритма выбора базового элемента. В идеале следовало бы выбирать средний элемент списка. Затем при разбиении количество элементов в наборе значений, меньших значения базового элемента, будет равно количеству элементов в наборе значений, больших значения базового элемента. Другими словами, при разбиении исходный список был бы разделен на две равные половины. Вычисление среднего элемента списка (или его медианы) представляет собой достаточно сложный процесс, к тому же стандартный алгоритм его определения использует метод разбиения быстрой сортировки, который мы сейчас обсуждаем. Поэтому нам придется отказаться от определения среднего элемента списка.
Худшим случаем будет иметь место, если в качестве базового элемента мы выберем элемент с максимальным или минимальным значением. В этом случае после выполнения процесса разбиения один из результирующих списков будет пуст, а во втором будут содержаться все элементы, поскольку все они будут находиться по одну сторону от базового элемента. Конечно, заранее (по крайней мере, без просмотра списка) невозможно узнать, выбран ли элемент с минимальными или максимальным значением, но если при каждом рекурсивном вызове в качестве базового элемента будет выбираться один из граничных элементов, то для n элементов будет выполнено n уровней рекурсии. При большом количестве сортируемых элементов это может вызывать проблемы. (при реализации алгоритма быстрой сортировки особое внимание следует уделить исключению возможности зацикливания рекурсивных вызовов.)
Таким образом, после рассмотрения этих двух граничных случаев можно сказать, что желательно выбирать базовый элемент, который был бы как можно ближе к среднему элементу и как можно дальше от минимального и максимального.
Во многих книгах в качестве базового элемента выбирается первый или последний элемент списка. Если в исходном списке элементы располагались в произвольном порядке, стратегия выбора первого или последнего элемента ничем не отличается от любой другой. Но если исходный список был отсортирован в прямом или обратном порядке, выбор в качестве базового элемента первого или последнего элемента списка приводит нас к наихудшему случаю для алгоритма быстрой сортировки. Следовательно, первый или последний элемент нежелательно выбирать в качестве базового. Никогда так не делайте.
