Быстрая сортировка
Эта статья находится в разработке!
Быстрая сортировка(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за , среднее время работы , что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
Алгоритм
- Выбираем опорный элемент.
- Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
- Рекурсивно сотрируем "маленькие" и "большие" элементы.
var
a : array [ 1 . .N] of integer ;
procedure QSort ( left , right : integer ) ;
var
i , j : integer ;
key : integer ;
buf : integer ;
begin
key := a [ random ( right - left + 1) + left ] ;
i := left ;
j := right ;
repeat
while a [ i ] < key do
inc ( i ) ;
while key < a [ j ] do
dec ( j ) ;
if i <= j then begin
buf := a [ i ] ;
a [ i ] := a [ j ] ;
a [ j ] := buf ;
inc ( i ) ;
dec ( j ) ;
end ;
unti l i > j ;
if left < j then
QSort ( left , j ) ;
if i < right then
QSort ( i , right ) ;
end ;
begin
. . .
QSort ( 1 , N) ;
end .
Оптимизация глубины рекурсии до O(logn) в худшем случае
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь . Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
Асимптотика
Oh, boy, here we go!
Худшее время работы
Обозначим худшее время работы за . Получим рекуррентное соотношение
Предположим, что . Тогда получим
Таким образом
