Викиконспекты - Вклад участника [ru]

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

2014-10-27T16:41:08Z

78.25.122.56: /* Разбиение массива */

'''Быстрая сортировка''' (qsort, сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.

==Алгоритм==
* из массива выбирается некоторый опорный элемент <tex>a[i]</tex>.
* запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные <tex>a[i]</tex>, влево от него, а все ключи, большие, либо равные <tex>a[i]</tex> {{---}} вправо.
* для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру..

==Псевдокод==
'''function''' quicksort(A, l, r):
'''if''' l < r
q = partition(A, l, r)
quicksort(A, l, q - 1)
quicksort(A, q + 1, r)
Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(A, 0, length[A] - 1)}</tex>.

===Разбиение массива===
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>A[p..r]</tex> нужным образом:
'''int''' partition(A, l, r):
x = A[l]
i = l
j = r
'''while''' ''true''
'''while''' A[i] < x
i = i + 1
'''while''' A[j] > x
j = j - 1
'''if''' i < j
swap(A[i++], A[j--])
'''else'''
'''return''' j

==Асимптотика==
===Худшее время работы===
Предположим, что мы разбиваем массив так, что одна часть содержит <tex>n - 1</tex> элементов, а вторая {{---}} <tex>1</tex>. Поскольку процедура разбиения занимает время <tex>\Theta(n)</tex>, для времени работы <tex>T(n)</tex> получаем соотношение:

<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>.

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

===Среднее время работы===
{{
Лемма
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.

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

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

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

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

<tex>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</tex> сравнивается с <tex>z_j\}</tex>

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

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

<tex> 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} < \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)</tex>
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.

==Улучшения==
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>, а время работы алгоритма <tex>O(n^2)</tex>. Существуют различные способы разбиения массива, направленные против худшего случая:
* При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — <tex>O(n \log n)</tex>.
* Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов).
* Разбивать массив не на две, а на три части.

==Оптимизация глубины рекурсии до O(logn) в худшем случае==
Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.

== Источники информации ==
* [[wikipedia:Быстрая сортировка|Википедия {{---}} быстрая сортировка]]
* [[wikipedia:Quicksort|Wikipedia {{---}} Quicksort]]
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]

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

2014-10-27T16:39:43Z

78.25.122.56: /* Разбиение массива */

'''Быстрая сортировка''' (qsort, сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.

==Алгоритм==
* из массива выбирается некоторый опорный элемент <tex>a[i]</tex>.
* запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные <tex>a[i]</tex>, влево от него, а все ключи, большие, либо равные <tex>a[i]</tex> {{---}} вправо.
* для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру..

==Псевдокод==
'''function''' quicksort(A, l, r):
'''if''' l < r
q = partition(A, l, r)
quicksort(A, l, q - 1)
quicksort(A, q + 1, r)
Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(A, 0, length[A] - 1)}</tex>.

===Разбиение массива===
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>A[p..r]</tex> нужным образом:
'''int''' partition(A, l, r):
x = A[l]
i = l
j = r
'''while''' ''true''
'''while''' A[i] < x
i = i + 1
'''while''' A[j] > x
j = j - 1
'''if''' i < j
swap(A[i++], A[j++])
'''else'''
'''return''' j

==Асимптотика==
===Худшее время работы===
Предположим, что мы разбиваем массив так, что одна часть содержит <tex>n - 1</tex> элементов, а вторая {{---}} <tex>1</tex>. Поскольку процедура разбиения занимает время <tex>\Theta(n)</tex>, для времени работы <tex>T(n)</tex> получаем соотношение:

<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>.

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

===Среднее время работы===
{{
Лемма
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.

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

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

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

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

<tex>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</tex> сравнивается с <tex>z_j\}</tex>

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

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

<tex> 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} < \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)</tex>
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.

==Улучшения==
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>, а время работы алгоритма <tex>O(n^2)</tex>. Существуют различные способы разбиения массива, направленные против худшего случая:
* При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — <tex>O(n \log n)</tex>.
* Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов).
* Разбивать массив не на две, а на три части.

==Оптимизация глубины рекурсии до O(logn) в худшем случае==
Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.

== Источники информации ==
* [[wikipedia:Быстрая сортировка|Википедия {{---}} быстрая сортировка]]
* [[wikipedia:Quicksort|Wikipedia {{---}} Quicksort]]
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]