Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Алгоритм быстрой сортировки был разработан К.A.Р. Хоаром (C.A.R. Hoare) в 1960 году. Этот алгоритм, наверное, еще более известен, чем пузырьковая сортировка. В настоящее время он является самым широко используемым в программировании методом сортировки, что вызвано его крайне положительными характеристиками: это алгоритм класса O(n log(n)) для общего случая, он требует лишь незначительного объема дополнительной памяти, работает с различными типами входных списков и достаточно удобен для реализации. Но, к сожалению, быстрая сортировка имеет и несколько нежелательных характеристик: при его реализации допускается очень много ошибок (простые ошибки в реализации могут остаться незамеченными и при выполнении могут потребовать дополнительного времени), быстродействие в худшем случае составляет O(n(^2^)) и к тому
Кроме того, быстрая сортировка наиболее изучена. Со времени выхода в свет первой статьи Хоара многие исследователи изучали быструю сортировку и сформировали значительную базу данных по теоретическому определению времени выполнения, подкрепленную эмпирическими данными. Было предложено немало улучшений базового алгоритма, позволяющих увеличить скорость работы. Некоторые из предложенных улучшений будет рассмотрены в этой главе. При таком богатстве литературных источников по алгоритму быстрой сортировки, если следовать всем рекомендациям, у вас не должно возникнуть проблем с реализацией. (В последней оптимизированной реализации алгоритма использовалось более шести различных справочных пособий по алгоритмам. Причем в одной из них была приведена "оптимизированная" быстрая сортировка, которая была написана так плохо, что при одних и тех же входных данных работала даже медленнее, чем стандартный метод TList.Sort.)
Быстрая сортировка встречается везде. Во всех версиях Delphi, за исключением версии 1, метод TList.Sort реализован на основе алгоритма быстрой сортировки. Метод TStringList.Sort во всех версиях Delphi реализован с помощью быстрой сортировки. В С++ функция qsort из стандартной библиотеки времени выполнения также реализована на базе быстрой сортировки.
Основной алгоритм быстрой сортировки, как и сортировку слиянием, можно отнести к классу "разделяй и властвуй". Он разбивает исходный список на два, а затем для выполнения сортировки рекурсивно вызывает сам себя для каждой части списка. Таким образом, особое внимание в быстрой сортировке нужно уделить процессу разделения. В разбитом списке происходит следующее: выбирается элемент, называемый базовым, относительно которого переставляются элементы в списке. Элементы, значения которых меньше, чем значение базового элемента, переносятся левее базового, а элементы, значения которых больше, чем значение базового элемента, переносятся правее базового. После этого можно сказать, что базовый элемент находится на своем месте в отсортированном списке. Затем выполняется рекурсивный вызов функции быстрой сортировки для левой и правой частей списка (относительно базового элемента). Рекурсивные вызовы прекращаются, когда список, переданный функции сортировки, будет содержать всего один элемент, а, следовательно, весь список оказывается отсортированным.
Таким образом, для выполнения быстрой сортировки необходимо знать два алгоритма более низкого уровня: как выбирать базовый элемент и как наиболее эффективно переставить элементы списка таким образом, чтобы получить два набора элементов: со значениями, меньшими, чем значение базового элемента, и со значениями, большими, чем значение базового элемента.
Начнем с описания алгоритма выбора базового элемента. В идеале следовало бы выбирать средний элемент списка. Затем при разбиении количество элементов в наборе значений, меньших значения базового элемента, будет равно количеству элементов в наборе значений, больших значения базового элемента. Другими словами, при разбиении исходный список был бы разделен на две равные половины. Вычисление среднего элемента списка (или его медианы) представляет собой достаточно сложный процесс, к тому же стандартный алгоритм его определения использует метод разбиения быстрой сортировки, который мы сейчас обсуждаем. Поэтому нам придется отказаться от определения среднего элемента списка.
Худшим случаем будет иметь место, если в качестве базового элемента мы выберем элемент с максимальным или минимальным значением. В этом случае после выполнения процесса разбиения один из результирующих списков будет пуст, а во втором будут содержаться все элементы, поскольку все они будут находиться по одну сторону от базового элемента. Конечно, заранее (по крайней мере, без просмотра списка) невозможно узнать, выбран ли элемент с минимальными
Таким образом, после рассмотрения этих двух граничных случаев можно сказать, что желательно выбирать базовый элемент, который был бы как можно ближе к среднему элементу и как можно дальше от минимального и максимального.
Во многих книгах в качестве базового элемента выбирается первый или последний элемент списка. Если в исходном списке элементы располагались в произвольном порядке, стратегия выбора первого или последнего элемента ничем не отличается от любой другой. Но если исходный список был отсортирован в прямом или обратном порядке, выбор в качестве базового элемента первого или последнего элемента списка приводит нас к наихудшему случаю для алгоритма быстрой сортировки. Следовательно, первый или последний элемент нежелательно выбирать в качестве базового. Никогда так не делайте.
Намного лучше в качестве базового элемента брать средний элемент исходного списка. Остается только надеяться, что он будет находиться вблизи среднего элемента списка. В списке, элементы которого не упорядочены, выбор базового элемента не имеет значения, но если список уже отсортирован в прямом или обратном порядке, средний элемент будет лучшим выбором.
После выбора базового элемента можно перейти к описанию алгоритма разбиения списка. Добро пожаловать в известные своей быстротой внутренние циклы быстрой сортировки! Мы будем оперировать с двумя индексами: первый будет использоваться для прохождения по элементам списка слева направо, а второй -справа налево. Начинаем справа, и идем к левому краю списка, сравнивая значение каждого элемента со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого меньше или равно значению базового элемента. Это был внутренний цикл 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;
{выполнить быструю сортировку первого подфайла}