Быстрая сортировка
Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще
остаются. Один из наиболее известных алгоритмов сортировки - быстрая сортировка,
предложенная Ч.Хоором. Метод и в самом деле очень быстр, недаром по-английски
его так и величают QuickSort к неудовольствию всех спелл-чекеров ("...Шишков
прости: не знаю, как перевести").
Этому методу требуется O(n lg n) в среднем
и O(n2) в худшем случае. К счастью, если
принять адекватные предосторожности, наихудший случай крайне маловероятен.
Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т.е.
он не является и методом сортировки на месте. Дальнейшую информацию можно
получить в работе Кормена
[1990].
Теория
Алгоритм разбивает сортируемый массив на разделы, затем рекурсивно сортирует
каждый раздел. В функции Partition (рис. 2.3) один из элементов массива
выбирается в качестве центрального. Ключи, меньшие центрального следует
расположить слева от него, те, которые больше, - справа.
реализации алгоритма на Си операторы
typedef T и
compGT следует изменить так, чтобы они соответствовали
данным, хранимым в массиве. По сравнению с основным алгоритмом имеются
некоторые улучшения:
-
В качестве центрального в функции partition выбирается элемент,
расположенный в середине. Такой выбор улучшает оценку среднего времени
работы, если массив упорядочен лишь частично. Наихудшая для этой реализации
ситуация возникает в случае, когда каждый раз при работе partition
в качестве центрального выбирается максимальный или минимальный элемент.
-
Для коротких массивов вызывается insertSort. Из-за рекурсии и других
"накладных расходов" быстрый поиск оказывается не столь уж быстрым для
коротких массивов. Поэтому, если в массиве меньше 12 элементов, вызывается
сортировка вставками. Пороговое значение не критично - оно сильно зависит
от качества генерируемого кода.
-
Если последний оператор функции является вызовом этой функции, говорят
о хвостовой рекурсии. Ее имеет смысл заменять на итерации - в этом случае
лучше используется стек. Это сделано при втором вызове QuickSort
на рис. 2.3.
-
После разбиения сначала сортируется меньший раздел. Это также приводит
к лучшему использованию стека, поскольку короткие разделы сортируются быстрее
и им нужен более короткий стек.
Функция qsort из стандартной библиотеки
Си основана на алгоритме quicksort. Для этой реализации рекурсия была заменена
на итерации. В таблице 2.1 приводится время и размер стека, затрачиваемые
до и после описанных улучшений.
Оглавление
