Изменения

Он делит сортируемый массив на две части, затем сортирует эти части независимо друг от друга. Как будет показано далее, точное положение точки деления зависит от исходного порядка элементов во входном файле. Суть метода заключается в процессе разбиения файла, который переупорядочивает файл таким образом, что выполняются следующие условия: ¦ Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве. ¦ Ни один из элементов a[i],..., a[i-l] не пре- вышает a[i]. м Ни один из элементов a[i+l],..., а[г] не явля- ется меньшим a[i].   * Массив <tex> a[l \ldots r]</tex> типа <tex> 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> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.

'''void''' quicksort(a: '''intT'''[n], '''int''' l, '''int''' r)

'''int''' q = partition(a, l, r) quicksort(a, l, q - 1)

Основной шаг алгоритма сортировки {{---}} процедура <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: '''intT'''[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)

i = i + 1+

j = j - 1 '''if''' (j == l) '''break'''-

swap(a[i++], a[j]) swap(a[i], a[r--]) '''return''' ij

'''void''' antiQsort(a: '''intT'''[n])

|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

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

Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное максимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).

|proof=Пусть Х <tex>X</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.

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

'''void''' quicksort(a: '''intT'''[n], '''int''' l, '''int''' r)

s.push(l, r); '''while''' (!s.empty()isNotEmpty) (l = s.pop(, r) r = s.pop()

'''int''' i = partition(a, l, r); '''if''' (i - 1 l > r - i)

привести к существенному повышению эффективности быстрой сортировки. Данная реализация осуществляет разделение по медиане из первогоФункция <tex>\mathrm{median}</tex> возвращает индекс элемента, среднего являющегося медианой трех элементов. После этого он и последнего элементов средний элемент массиваменяются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex>M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].

'''void''' quicksort(a: '''intT'''[n], '''int''' l, '''int''' r) '''if''' (r - 1 l <tex> \leqslant </tex> M) insertion(a, l, r)

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)

'''void''' hybridsort(a: '''int'''[n]Вообще, '''int''' lможно применять любые эвристики по выбору опорного элемента. Например, '''int''' r) quicksort(aв стандартной реализации в Java в качестве разделяющего выбирается средний из 7 элементов, l, r) insertion(a, l, r)равномерно распределённых по массиву.

на элементы,меньшие разделяющего элемента <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>]]

окончательные позиции. После этого указанные ключи могут быть исключены из подмассивов, для которых выполняются последующие рекурсивные вызовы.

'''void''' quicksort(a: '''intT'''[n], '''int''' l, '''int''' r) '''int''' k '''intT''' v = a[r]

'''while''' ''true(i <tex> \leqslant </tex> j)'' '''while''' (a[i] < v)

'''while''' (a[j] > v)

'''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)