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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Среднее время работы)
(Среднее время работы)
Строка 39: Строка 39:
 
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
 
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
 
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.
 
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.
 +
 +
Заметим, что сравнеие каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении.
  
 
Поскольку каждая пара элементов срановается не более одного раза, полное количество сравнений выражается как
 
Поскольку каждая пара элементов срановается не более одного раза, полное количество сравнений выражается как

Версия 00:53, 16 июня 2011

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

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

Алгоритм

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

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

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

Асимптотика

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

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

[math]T(n) = Max(T(q)+T(n-q-1))+\Theta(n)[/math],где [math]0 \leq q \leq n-1[/math], так как мы разбиваемся на 2 подзадачи.

Предположим, что [math]T(n) \leq c(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]q^2+(n-q-1)^2[/math] принимает максимальное значение на концах интервала [0; n-1], что позволяет нам сделать оценку

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

Подставим это в наше выражение для [math]T(n)[/math]

[math]T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2[/math]

Таким образом [math]T(n) = O(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]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]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]

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

Ссылки

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

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

Литература

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