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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Разбиение массива)
(Худшее время работы)
Строка 38: Строка 38:
 
==Асимптотика==
 
==Асимптотика==
 
===Худшее время работы===
 
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение  
+
Предположим, что мы разбиваем массив так, что одна часть содержит <tex>n - 1</tex> элементов, а вторая {{---}} <tex>1</tex>. Поскольку процедура разбиения занимает время <tex>\Theta(n)</tex>, для времени работы <tex>T(n)</tex> получаем соотношение:
  
<tex>T(n) = \max(T(q)+T(n-q-1))+\Theta(n)</tex>, где <tex>0 \leq q \leq n-1</tex>,
+
<tex>T(n) = T(n - 1) + \Theta(n)</tex>
так как мы разбиваемся на 2 подзадачи.
 
  
Предположим, что <tex>T(n) \leq c(n^2)</tex>. Тогда получим
+
Поскольку <tex>T(n) = \Theta(n)</tex>, имеем
  
<tex>T(n) \leq \max(cq^2+c(n-q-1)^2)+\Theta(n) =  
+
<tex>T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)</tex>.
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>
 
  
Заметим, что <tex>q^2+(n-q-1)^2</tex> принимает максимальное значение на концах интервала [0; n-1], что позволяет нам сделать оценку
+
Мы видим, что при максимально несбалансированном разбиении время работы составляет <tex>\Theta(n^2)</tex>. В частности, это происходит, если массив изначально отсортирован.
 
 
<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>
 
 
 
Подставим это в наше выражение для <tex>T(n)</tex>
 
 
 
<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
 
 
 
Таким образом <tex>T(n) = O(n^2)</tex>.
 
  
 
===Среднее время работы===
 
===Среднее время работы===

Версия 19:29, 29 мая 2012

Быстрая сортировка (qsort, сортировка Хоара) — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(n\log{n})[/math], что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из [math]n[/math] элементов в худшем случае может составить [math]\Theta(n^2)[/math], на практике этот алгоритм является одним из самых быстрых. Кроме того, быстрая сортировка не требует дополнительной памяти.

Алгоритм

  • из массива выбирается некоторый опорный элемент [math]a[i][/math].
  • запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные [math]a[i][/math], влево от него, а все ключи, большие, либо равные [math]a[i][/math] — вправо.
  • для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру..

Псевдокод

<wikitex>

Quicksort(A, p, r)
    if p < r
        then q = Partition(A, p, r)
            Quicksort(A, p, q)
            Quicksort(A, q + 1, r)

</wikitex> Для сортировки всего массива необходимо выполнить процедуру [math]Quicksort(A, 1, length[A])[/math].

Разбиение массива

Основной шаг алгоритма сортировки — процедура [math]Partition[/math], которая переставляет элементы массива [math]A[p..r][/math] нужным образом: <wikitex>

Partition(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while true
        do repeat j = j - 1
            until A[j] [math]\leq[/math] x
            repeat i = i + 1
                until A[i] > x
            if i < j
                then поменять A[i] и A[j]
                else return j

</wikitex>

Оптимизация глубины рекурсии до O(logn) в худшем случае

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

Асимптотика

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

Предположим, что мы разбиваем массив так, что одна часть содержит [math]n - 1[/math] элементов, а вторая — [math]1[/math]. Поскольку процедура разбиения занимает время [math]\Theta(n)[/math], для времени работы [math]T(n)[/math] получаем соотношение:

[math]T(n) = T(n - 1) + \Theta(n)[/math]

Поскольку [math]T(n) = \Theta(n)[/math], имеем

[math]T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)[/math].

Мы видим, что при максимально несбалансированном разбиении время работы составляет [math]\Theta(n^2)[/math]. В частности, это происходит, если массив изначально отсортирован.

Среднее время работы

Лемма:
Пусть Х — полное количество сравнений элементов с опорным за время работы сортировки. Тогда время работы сортировки равно [math]O(n \log n)[/math].
Доказательство:
[math]\triangleright[/math]

Нам необходимо вычислить полное количество сравнений. Переименуем элементы массива как [math]z_1...z_n[/math], где [math]z_i[/math] наименьший по порядку элемент. Также введем множество [math]Z_{ij} = \{z_i, z_{i+1}...z_j\}[/math].

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

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

[math]X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}[/math], где [math]X_{ij} = 1[/math] если произошло сравнение [math]z_i[/math] и [math]z_j[/math] и [math]X_{ij} = 0[/math], если сравнения не произошло.

Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим

[math]E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i[/math] сравнивается с [math]z_j\}[/math]

Осталось вычислить величину [math]Pr\{z_i[/math] сравнивается с [math]z_j\}[/math] - вероятность того, что [math]z_i[/math] сравнивается с [math]z_j[/math]. Поскольку предполагается, что все элементы в массиве различны, то при выборе [math]x[/math] в качестве опорного элемента впоследствии не будут сравниваться никакие [math]z_i[/math] и [math]z_j[/math] для которых [math]z_i \lt x \lt z_j[/math]. С другой стороны, если [math]z_i[/math] выбран в качестве опорного, то он будет сравниваться с каждым элементом [math]Z_{ij}[/math] кроме себя самого. Таким образом элементы [math]z_i[/math] и [math]z_j[/math] сравниваются тогда и только тогда когда первым в множестве [math]Z_{ij}[/math] опорным элементом был выбран один из них.

[math]Pr\{z_i[/math] сравнивается с [math]z_j\} = Pr\{[/math] первым опорным элементом был [math]z_i[/math] или [math]z_j\} = Pr\{[/math] первым опорным элементом был [math]z_i\} + Pr\{[/math] первым опорным элементом был [math]z_j\} = \frac {1}{j-i+1} + \frac {1}{j-i+1} = \frac {2}{j-i+1} [/math]

[math] E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} \lt \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)[/math]
[math]\triangleleft[/math]

Mатожидание времени работы быстрой сортировки будет [math]O(n \log n)[/math].

Ссылки

Литература

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