Самые быстрые алгоритмы сортировки

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

Поразрядная цифровая сортировка. Алгоритм поразрядной цифровой сортировки относится к распределительным, и требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов равно максимальному числу значащих цифр в числе – D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу.

Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.

Порядок алгоритма качественно линейный – O(n), для сортировки требуется D·n операций анализа цифры. Однако в оценке порядка не учитывается ряд обстоятельств. Во-первых, операция выделения значащей цифры будет простой и быстрой только при P=2, для других систем счисления эта операция может оказаться значительно более времяемкой, чем операция сравнения. Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп.

Размещение групп в статической рабочей памяти потребует памяти для P·n элементов, так как в предельном случае все элементы могут попасть в какую-то одну группу. Если же формировать группы внутри той же последовательности по принципу обменных алгоритмов, то возникает необходимость перераспределения последовательности между группами и все недостатки, присущие алгоритмам включения. Наиболее рациональным является формирование групп в виде связных списков с динамическим выделением памяти.

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

Const

D=...; { Максимальное количество цифр в числе }

P=...; { Основание системы счисления }

{ Возвращает значение n-ой цифры в числе v }

function Digit(v, n: Integer): Integer;

Begin

for n:=n downto 2 do

v:=v div P;

Digit:=v mod P;

end;

procedure Sort(var a: TA);

Var

{ Индекс элемента, следующего за последним в i-ой группе }

b: array[0..P-2] of Integer;

i, j, k, m, x: Integer;

Begin

{ Перебор цифр, начиная с младшей }

for m:=1 to D do

Begin

{ Начальные значения индексов }

for i:=0 to P-2 do b[i]:=1;

{ Перебор массива }

for i:=1 to N do

Begin

{ Определение m-ой цифры }

k:=Digit(a[i],m);

x:=a[i];

{ Сдвиг - освобождение места в конце k-ой группы }

for j:=i downto b[k]+1 do

a[j]:=a[j-1];

{ Запись в конец k-ой группы }

a[b[k]]:=x;

{ Модификация k-го индекса и всех больших }

for j:=k to P-2 do

b[j]:=b[j]+1;

end;

end;

end;

Область памяти, занимаемая массивом, перераспределяется между входным и выходным множествами. Выходное множество размещается в начале массива и разбивается на группы. Разбиение отслеживается в массиве b. Элемент массива b[i] содержит индекс в массиве a, с которого начинается i+1-я группа. Номер группы определяется значением анализируемой цифры числа, поэтому индексация в массиве b начинается с 0.

Когда очередное число выбирается из входного множества и должно быть занесено в i-ю группу выходного множества, оно будет записано в позицию, определяемую значением b[i]. Но предварительно эта позиция должна быть освобождена: участок массива от b[i] до конца выходного множества включительно сдвигается вправо. После записи числа в i-ю группу i-е и все последующие значения в массиве b корректируются – увеличиваются на 1.

Результаты трассировки при P=10 и D=4 представлены в табл. 4.12.

Табл. 4.12. Трассировка цифровой сортировки.

Быстрая сортировка Хоараотносится к распределительным и обеспечивает показатели эффективности O(n·log₂(n)) даже при наихудшем исходном распределении. Алгоритм был разработан Хоаром в 1960 г. Алгоритм требует незначительной дополнительной памяти и относительно в реализации. Однако при реализации допускается много ошибок, которые могут остаться незамеченными и требовать дополнительного времени при выполнении, быстродействие в худшем случае может достигать показателя O(n²) и к тому же алгоритм относится к группе неустойчивых.

Тем не менее, сортировка Хоара в различных модификациях очень широко применяется. Во всех версиях Delphi методы TList.Sort и TStringList.Sort реализованы на основе быстрой сортировки. В C++ функция qsort из стандартной библиотеки времени выполнения также реализована на основе быстрой сортировки. Большое количество литературных источников по алгоритму быстрой сортировки позволяет корректно реализовать алгоритм и изучить многие особенности его работы.

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

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

Таким образом, для выполнения быстрой сортировки необходимо знать два алгоритма более низкого порядка: метод выбора базового элемента и метод эффективной перестановки элементов списка.

Лучшим случаем выбора базового элемента является медиана – средний элемент отсортированного списка. Тогда количество элементов в обоих подсписков будет одинаковым. Однако процесс поиска медианы сводится к алгоритму быстрой сортировки, поэтому неприемлем.

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

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

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

{ Быстрая сортировка Хоара с выбором

среднего элемента в качестве базового }

procedure QuickHoarStd1Sort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

L, R: Integer;

M, Temp: Pointer;

Begin

if aFirst >= aLast then Exit;

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

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

{ Начальные значения индексов }

L:=aFirst-1; R:=aLast+1;

{ Приступить к разбиению списка }

while True do

Begin

repeat Dec(R);

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

repeat Inc(L);

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

if L >= R then Break;

Temp:=aList.List[L];

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

aList.List[R]:=Temp;

end;

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

QuickHoarStd1Sort(aList, aFirst, R, aCompare);

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

QuickHoarStd1Sort(aList, R+1, aLast, aCompare);

end;

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

После завершения обоих внутренних циклов возможны два исхода. В первом случае индекс L меньше индекса R, т.е. два элемента, на которые указывают индексы, расположены в неверном порядке. Тогда следует поменять расположение элементов и продолжить выполнение внутренних циклов. Во втором случае индексы равны или пересеклись – значение левого индекса равно или превосходит значение правого. Следовательно, список успешно разделен, и выполнение циклов можно прервать. После выхода из бесконечного цикла рекурсивно применяется тот же алгоритм для левого и правого подсписка.

Результаты трассировки приведены в табл. 4.13. В каждой строке таблицы показаны текущие положения индексов L и R, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.

Таблица 4.13. Трассировка сортировки Хоара.

Незначительная модификация алгоритма позволит избавиться от одного рекурсивного вызова. В следующем примере используется цикл while совместно с изменением значения переменной aFirst. В результате левые подсписки будут обрабатываться рекурсивно, а правые – итеративно.

{ Быстрая сортировка Хоара (без одной рекурсии) }

procedure QuickHoarStd2Sort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

L, R: Integer;

M, Temp: Pointer;

Begin

{ Повторять, по в списке

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

while (aFirst < aLast) do

Begin

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

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

{ Начальные значения индексов }

L:=aFirst-1; R:=aLast+1;

{ Приступить к разбиению списка }

while True do

Begin

repeat Dec(R);

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

repeat Inc(L);

until aCompare(aList.List[L], M) >= 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

QuickHoarStd2Sort(aList, aFirst, R, aCompare);

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

aFirst:=R+1;

end;

end;

Другая незначительная модификация состоит в выборе базового элемента случайным образом: случайно выбранный элемент меняется местом со средним и становится базовым. При наличии хорошего генератора псевдослучайных чисел вероятность попадания на худший случай (граничное значение) становится пренебрежимо мало. Заметим, однако, что понижение вероятности не повышает скорость выполнения алгоритма в целом. Пример реализации алгоритма со случайным выбором базового элемента приведен ниже.

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

procedure QuickHoarRNDSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

L, R: Integer;

M, Temp: Pointer;

Begin

while aFirst < aLast do

Begin

{ Начало добавляемой части }

{ Выбрать случайный элемент, переставить его со

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

R:=aFirst + Random(aLast - aFirst + 1);

L:=(aFirst + aLast) div 2;

M:=aList.List[R];

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

aList.List[L]:=M;

{ Конец добавляемой части }

L:=aFirst-1;

R:=aLast+1;

while True do

Begin

repeat Dec(R);

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

repeat Inc(L);

until aCompare(aList.List[L], M) >= 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

QuickHoarRNDSort(aList, aFirst, R, aCompare);

aFirst:=R+1;

end;

end;

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