Быстрая сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Ссылки)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
+
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
  
 
==Алгоритм==
 
==Алгоритм==
Строка 45: Строка 45:
  
 
==Асимптотика==
 
==Асимптотика==
Oh, boy, here we go!
 
 
===Худшее время работы===
 
===Худшее время работы===
 
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение  
 
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение  
Строка 64: Строка 63:
 
   
 
   
 
http://en.wikipedia.org/wiki/Quicksort
 
http://en.wikipedia.org/wiki/Quicksort
 +
 +
==Литература==
 +
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7

Версия 20:32, 15 июня 2011

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

Быстрая сортировка(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