Изменения

Он делит сортируемый массив * Массив <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> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.

'''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завершается.

'''T''' v = a[(l + r) / 2]

'''int''' j = r - 1 '''while''' ''true'' (i <tex> \leqslant </tex> j) '''while''' (a[i++] < v) i++ '''while''' (a[j--] > v) '''if''' ( j == l) '''break'''--

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

|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> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.

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

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>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более n <tex>1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.

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

'''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: '''T'''[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>]]

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

'''while''' ''true(i <tex> \leqslant </tex> j)'' '''while''' (a[i++] < v) i++ '''while''' (a[j--] > v) '''if''' (i == j) '''break'''--

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