Изменения
→Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента
Основной шаг алгоритма сортировки {{---}} процедура <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>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.
'''while''' (a[j] > v)
j--
'''if''' (i <tex> \leqslant geqslant </tex> j) '''break''' swap(a[i++], a[j--])
'''return''' j
! Шаг 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>.
<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>
'''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>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n 1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
===Улучшенная быстрая сортировка===
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может
привести к существенному повышению эффективности быстрой сортировки. Функция <tex>\mathrm{median}</tex> возвращает индекс среднего элемента в массиве, являющегося медианой трех элементов. После этого он и крайний правый средний элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex> M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].
'''const int''' M = 10
'''if''' (r - l <tex> \leqslant </tex> M)
insertion(a, l, r)
'''return'''
'''int''' med = median(a[l], a[(l + r) / 2], a[r])
swap(a[med], a[(l + r) / 2])
'''int''' i = partition(a, l + 1, r - 1) quicksort(a, l, i - 1)
quicksort(a, i + 1, r)
'''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 = 1l; 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)
Для предотвращения ухудшения времени работы быстрой сортировки до <tex>O(n^2)</tex> при неудачных входных данных, также можно использовать алгоритм сортировки Introsort.
Он использует быструю сортировку и переключается на [[Сортировка кучей|пирамидальную сортировку]], когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Пирамидальная Так как после нескольких итераций быстрой сортировки с применением разных эвристик массив с большей вероятностью окажется «почти отсортированным», то пирамидальная сортировка может довольно быстро закончить дело. Также, пирамидальная сортировка хороша тем, что требует <tex>O(1)</tex> дополнительной памяти, в отличие от, например, сортировки слиянием, где потребуется <tex>O(n)</tex> дополнительной памяти.
==См. также==
