Быстрая сортировка. 
Сортировки одномерного массива

Этот улучшенный метод сортировки основан на обмене. Это самый лучший из всех известных на данный момент методов сортировки массивов. Был разработан в 1962 г. Его производительность столь впечатляюща, что изобретатель Ч. Хоар назвал этот метод быстрой сортировкой (Quicksort).

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

Таким образом, процедура сортировки должна принимать указатель на массив и две переменные, обозначающие левую и правую границу сортируемой области.

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

Наиболее часто используется середина области, т. е. элемент с индексом (l + r)/2. При таком подходе используются быстрые операции сложения и деления на два, и в целом он работает достаточно неплохо. Однако в некоторых задачах, где сутью является исключительно сортировка, хитрое жюри специально подбирает тесты так, чтобы «завалить» стандартную быструю сортировку с выбором опорного элемента из середины. Стоит заметить, что это очень редкая ситуация, но все же стоит знать, что можно выбирать произвольный элемент с индексом т так, чтобы выполнялось неравенство l? т? r. Чтобы это условие выполнялось, достаточно выбрать произвольные два числа х и у и выбирать т исходя из следующего соотношения:

т = (х l + у r)/(х + у).

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

Приведем текст процедуры быстрой сортировки с выбором среднего элемента в качестве опорного:

procedure quick_sort (var a: list; left, right: integer);

var.

i, j, temp, p: integer;

begin.

i := left;

j := right;

p := a[(left+right) div 2];

repeat.

while (a[i] < p) do inc (i);

while (a[j] > p) do dec (j);

if (i <= j) then begin.

temp := a[i];

a[i] := a[j];

a[j] := temp;

inc (i);

dec (j);

end;

until (i > j);

if (j > left) then quick_sort (a, left, j);

if (i < right) then quick_sort (a, i, right);

end;

Чтобы воспользоваться быстрой сортировкой, необходимо передать в процедуру левую и правую границы сортируемого массива, (т.е., например, вызов для массива, а будет выглядеть как quick_sort (a, 0, n-1).

Алгоритм быстрой сортировки в среднем использует O (N logN) сравнений и O (N logN) присваиваний (на практике даже меньше) и использует O (logN) дополнительной памяти (стек для вызова рекурсивных процедур). В худшем случае алгоритм имеет сложность O (N2) и использует О (N) дополнительной памяти, однако вероятность возникновения худшего случая крайне мала: на каждом шаге вероятность худшего случая равна 2/N, где N — текущее количество элементов.

Рассмотрим возможные оптимизации метода быстрой сортировки.

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

Во-вторых, как мы знаем, вызов процедуры — достаточно накладная операция, а для небольших массивов быстрая сортировка работает не очень хорошо. Поэтому, если при вызове процедуры сортировки в массиве находится меньше, чем К элементов, разумно использовать какой-либо нерекурсивный метод, например, сортировку вставками или выбором. Число К при этом выбирается в районе 20, конкретные значения подбираются опытным путем. Такая модификация может дать до 15% прироста производительности.

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