Быстрая сортировка

Эта статья находится в разработке!

Быстрая сортировка(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(nlogn)[/math], что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.

Алгоритм

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

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) в худшем случае

В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь [math]O(n)[/math]. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.

Асимптотика

Худшее время работы

Обозначим худшее время работы за [math]T(n)[/math]. Получим рекуррентное соотношение [math]T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)[/math]

Предположим, что [math]T(n) \leq cO(n^2)[/math]. Тогда получим [math]T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) = cMax(q^2+(n-q-1)^2)+\Theta(n)[/math]

[math]Max(q^2+(n-q-1)^2) \leq (n-1)^2[/math]

[math]T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2[/math] Таким образом [math]T(n) = O(n^2)[/math]

Ссылки

http://ru.wikipedia.org/wiki/Быстрая_сортировка

http://en.wikipedia.org/wiki/Quicksort

Литература

• Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7