Изменения

Перейти к: навигация, поиск

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

2565 байт добавлено, 19:25, 4 сентября 2022
м
rollbackEdits.php mass rollback
==Алгоритм==
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".
Он делит сортируемый массив * Массив <tex> a[l \ldots r]</tex> типа T на две части, затем сортирует эти части независимо друг от друга. Как будет показано далее, точное положение точки деления зависит от исходного порядка элементов во входном файле. Суть метода заключается в процессе разбиения файла, который переупорядочивает файл таким образом, что выполняются следующие условия: ¦ Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве. ¦ Ни один из элементов a[i],..., a[i-l] не пре- вышает a[i]. м Ни один из элементов a[i+l],..., а[г] не явля- ется меньшим a[i].   * Массив <tex> a[l \ldots r]T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q-1]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q-1]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.* Подмассивы <tex> a[l \ldots q-1]</tex> и <tex> a[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным.
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''if''' l < r
'''int''' 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[l \ldots r]</tex> типа <tex> T </tex> нужным образом.Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а<tex> a[г(l + r) / 2] — он сразу займет свою окончательную позицию</tex>. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден эле- ментэлемент, превосходящий по значению разделяющий элемент, затем выполняется про- смотрпросмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разде- ленном разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[(l + r) / 2]</tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1</tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и ни один элемент справа от <tex> j </tex> не меньше <tex> v</tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершает- ся, меняя местами а[г] и a[i], при этом v присваивается зна- чение a[i], так что не будет ни одного большего элемента справа от v и ни одного меньшего элемента слева от vзавершается.
'''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r)
'''T''' v = a[(l + r) / 2]
'''int''' i = l
'''int''' j = r - 1 '''while''' ''true'' (i <tex> \leqslant </tex> j) '''while''' (a[i++] < v) i++ '''while''' (a[j--] > v) '''if''' ( j == l) '''break'''--
'''if''' (i <tex> \geqslant </tex> j)
'''break'''
swap(a[i++], a[j]) swap(a[i], a[r--]) '''return''' ij
==Асимптотика==
! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0
|-align="right"
|style="text-align: center;"|1 2 3 4 <br\> 0 '''0''' 0 0| style="text-align: center;"|1 2 3 4 <br\> 0 '''4''' 0 0|style="text-align: center;"|1 4 3 2 <br\> 0 0 0 '''4'''|style="text-align: center;"|1 4 3 2 <br\> 0 '''0''' 0 4|style="text-align: center;"|1 4 3 2 <br\> 0 '''3''' 0 4|style="text-align: center;"|1 3 4 2 <br\> 0 0 '''3''' 4|style="text-align: center;"|1 3 4 2 <br\> '''0''' 0 3 4
|-
! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат
|-align="right"
|style="text-align: center;"|1 3 4 2 <br\> '''2''' 0 3 4|style="text-align: center;"|3 1 4 2 <br\> 0 '''2''' 3 4|style="text-align: center;"|3 1 4 2 <br\> '''0''' 2 3 4|style="text-align: center;"|3 1 4 2 <br\> '''1''' 2 3 4|style="text-align: center;"|3 1 4 2 <br\> '''1''' 2 3 4| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br\> '''2 4 1 3'''
|-
</center>
Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное максимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).
Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.
Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.
Лемма
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть Х <tex>X</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1 \ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1} \ldots 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>
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''stack'''< '''pair'''<'''int''','''int'''> > s
s.push(l, r); '''while''' (!s.empty()isNotEmpty) (l = s.pop(, r) r = s.pop()
'''if''' (r <tex> \leqslant </tex> l)
'''continue'''
'''int''' i = partition(a, l, r); '''if''' (i - 1 l > r - i)
s.push(l, i - 1)
s.push(i + 1, r)
s.push(l, i - 1)
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более n <tex>1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
===Улучшенная быстрая сортировка===
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может
привести к существенному повышению эффективности быстрой сортировки. Данная реализация осуществляет разделение по медиане из первогоФункция <tex>\mathrm{median}</tex> возвращает индекс элемента, среднего являющегося медианой трех элементов. После этого он и последнего элементов средний элемент массиваменяются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex>M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].
'''const int''' M = 10
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''if''' (r - 1 l <tex> \leqslant </tex> M) insertion(a, l, r)
'''return'''
swap'''int''' med = median(a[l], a[(l + r)/2], a[r - 1]) medianswap(a[l], a[r - 1med], a[(l + r) / 2]) '''int''' i = partition(a, l + 1, r - 1) quicksort(a, l, i - 1)
quicksort(a, i + 1, r)
'''void''' hybridsort(a: '''T'''[n]Вообще, '''int''' lможно применять любые эвристики по выбору опорного элемента. Например, '''int''' r) quicksort(aв стандартной реализации в Java в качестве разделяющего выбирается средний из 7 элементов, l, r) insertion(a, l, r)равномерно распределённых по массиву.
===Быстрая сортировка с разделением на три части===
Когда в сортируемом массиве имеется множество повторяющихся ключей предыдущие реализации быстрой сортировки можно существенно улучшить. Например массив, который состоит из равных ключей, вовсе не нуждается в дальнейшей сортировке, однако предыдущие реализации продолжают процесс разделения, подвергая обработке все более мелкие подмассивы, независимо от того, насколько большим является исходный файл.
 
[[Файл:G3.png |400px|thumb|center|]]
В основу программы положено разделение массива на три части:
на элементы,меньшие разделяющего элемента <tex> a[l] \ldots a[ji]</tex>, элементы, равные разделяющему элементу <tex>a[ji+1] \ldots a[ij-1]</tex>,и элементы большие разделяющего элемента <tex>a[ij] \ldots a[r]</tex>.
После этого сортировка завершается двумя рекурсивными вызовами.
Просмотр массива начинается слева с целью обнаружить элемент, который не меньше разделяющего элемента, и справа с целью обнаружить элемент, который не больше разделяющего элемента, затем они меняются местами[[Файл:G3. Если после обмена элемент слева равен разделяющему элементу, он меняется местами с левымкрайним элементом png |400px|thumb|center| Разделение массива, то же самое проделывается и справа. <tex> a </tex>]]
Элементы массива равные разделяющему элементу находятся между <tex> l </tex> и <tex> p </tex> и между <tex> q </tex> и <tex> r </tex>. В разделяющем цикле, когда указатели просмотра перестают изменяться и выполняется обмен значениями <tex> i </tex> и <tex> j </tex>, каждый из этих элементов проверяется на предмет равенства разделяющему элементу. Если элемент, который сейчас находится слева, равен разделяющему элементу, то при помощи операции обмена он помещается в левую часть массива, если элемент, который сейчас находится справа, равен разделяющему элементу, то в результате операции обмена он помещается в правую часть массива.
После того как указатели пересекутся, элементы, равные разделяющему элементу и находящиеся на разных концах массива, после операции обмена попадают в свои
окончательные позиции. После этого указанные ключи могут быть исключены из подмассивов, для которых выполняются последующие рекурсивные вызовы.
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''int''' k
'''T''' v = a[r]
'''if''' (r <tex> \leqslant </tex> l)
'''int''' p = l - 1
'''int''' q = r
'''while''' ''true(i <tex> \leqslant </tex> j)'' '''while''' (a[i++] < v) i++ '''while''' (a[j--] > v) '''if''' (i == j) '''break'''--
'''if''' (i <tex> \geqslant </tex> j)
'''break'''
p++
swap(a[p], a[i])
i++
'''if''' (a[j] == v)
q--
swap(a[q], a[j])
j--
swap(a[i], a[r])
j = i - 1
i++
'''for''' ('''int''' k = 1 l; k <tex> \leqslant </tex> p; k++, j--) swap(a[k],a[j]) '''for''' ('''int''' k = r-1; k <tex> \geqslant </tex> q; k--, i++) swap(a[k],a[i]) quicksort(a, 1l, j)
quicksort(a, i, r)
 
===Параллельная сортировка===
 
Еще одной оптимизацией является [[PSRS-сортировка|параллельная сортировка]] на основе быстрой.
Пусть, исходный набор данных расположен на первом процессоре, с него начинается работа алгоритма. Затем исходный массив окажется разделенным на две части, меньшая из которых передастся другому свободному процессору, большая останется на исходном для дальнейшей обработки. Далее обе части опять будут разделены и опять на двух исходных останутся большие части, а меньшие отправятся другим процессорам. В этом заключается ускорение алгоритма. При задействовании всех процессоров, все части параллельно будут сортироваться последовательным алгоритмом.
 
===Introsort===
 
Для предотвращения ухудшения времени работы быстрой сортировки до <tex>O(n^2)</tex> при неудачных входных данных, также можно использовать алгоритм сортировки Introsort.
Он использует быструю сортировку и переключается на [[Сортировка кучей|пирамидальную сортировку]], когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как после нескольких итераций быстрой сортировки с применением разных эвристик массив с большей вероятностью окажется «почти отсортированным», то пирамидальная сортировка может довольно быстро закончить дело. Также, пирамидальная сортировка хороша тем, что требует <tex>O(1)</tex> дополнительной памяти, в отличие от, например, сортировки слиянием, где потребуется <tex>O(n)</tex> дополнительной памяти.
==См. также==
* [[Timsort]]
* [[Smoothsort]]
* [[PSRS-сортировка]]
== Источники информации ==
* [[wikipedia:ru:Быстрая сортировка|Википедия {{---}} Быстрая сортировка]]
* [[wikipedia:en:Quicksort|Wikipedia {{---}} Quicksort]]
* [[wikipedia:en:Introsort|Wikipedia {{---}} Introsort]]
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7
* ''Р. Седжвик'': Фундаментальные алгоритмы на С++ части 1 - 4
1632
правки

Навигация