Напомним, что в п. 7.3.4 рассмотрена внутренняя сортировка, особенностью которой является возможность использования некоторого дополнительного постоянного объема памяти для сортировки объектов. В алгоритме сортировки методом слияния такой механизм не применяется и, чтобы его использовать, требуется более сложный механизм слияния, чем описанный в п. 10.1.1. Внутренняя сортировка не является сложной по определению. Как и при пирамидальной сортировке, быстрая сортировка может быть адаптирована для внутренней сортировки.

Выполнение алгоритма внутренней быстрой сортировки требует определенной слаженности, так как для хранения подпоследовательностей при всех рекурсивных вызовах необходимо использовать саму исходную последовательность. Алгоритм inPlaceQuickSort для выполнения внутренней быстрой сортировки показан во фрагменте кода 10.6. Этот алгоритм предполагает, что исходная последовательность S содержит только уникальные элементы. Причина этого ограничения рассмотрена в упражнении М-10.11, а развитие данного общего случая — в упражнении 3-10.7. Алгоритм обращается к элементам исходной последовательности S с помощью методов, применяющих индексы. Следовательно, если S реализована массивом, он будет работать правильно.

Алгоритм inPlaceQuickSort(S,tf,?):

Input: последовательность S из уникальных элементов; целые числа а и Ь.

Output: последовательность S с элементами рангов а и b включительно, отсортированные в неубывающем порядке от а до Ь.

if a > b then return {пустой поддиапазон} p <- S.elemAtRank(b)- {точка отсчета} I <- а           {сканирование вправо}

г Ь — 1 {сканирование влево} while I < г do

{найти элемент больше точки отсчета} while / < г and S.elemAtRank(/) < р do / <- /+1

{найти элемент меньше точки отсчета} while г > / and S.elemAtRank(A) i р do г <- г – 1 if I < г then

S.swapElements(S.atRank(/),S.atRank(A)) {расположить точку отсчета в ее конечном положении} S.swapElements(S.atRank(/), S.atRank(b))

{рекурсивные обращения} inPlaceQuickSort(S, a, I – 1) inPlaceQuickSort(S, I + 1, b)

Фрагмент кода 10.6. для последовательности, реализованной массивом

изменяет исходную последовательность с помощью операции swapElements, не создавая при этом дополнительных подпоследовательностей. Подпоследовательности исходной последовательности неявно представлены перечнем позиций, определенных самым левым индексом / и самым правым индексом г. Стадия деления выполняется сканированием последовательности одновременно от / и г в обоих направлениях, меняя местами пары элементов, стоящих в обратном порядке относительно друг друга, как показано на рис. 10.13. Когда два таких индекса «встречаются», это означает, что подпоследовательности L и G расположены по обе стороны точки встречи. Алгоритм завершается рекурсией обеих последовательностей.

сокращает время выполнения, часть которого затрачивается на создание новых последовательностей) и перемещение элементов. Java-версия внутренней быстрой сортировки приводится во фрагменте кода 10.7.

//**

*                    Отсортировать элементы последовательности S в неубывающем

*                    порядке

*                    согласно компаратору с с помощью алгоритма внутренней быстрой

*                    сортировки

*                    выполняется вспомогательным рекурсивным методом quickSortStep.

** j

public static void quicksort (Sequence S, Comparator c) { if (S.size() < 2)

return; // последовательность с 0 или 1 элементом уже отсортирована quickSortStep(S, с, 0, S.size() – 1); // рекурсивный метод сортировки

}

//**

*                    Отсортировать в неубывающем порядке элементы

*                    последовательности S

*                    между рангами leftBound и rightBound с помощью рекурсивной

*                    реализации

*                    алгоритма внутренней быстрой сортировки. ** j

private static void quickSortStep (Sequence S, Comparator c,

int leftBound, int rightBound ) { if (leftBound >= rightBound)

Рис. 10.13. Стадия деления при быстрой сортировке на месте. Индекс / сканирует последовательность слева направо, индекс г — справа налево. Обмен элементов осуществляется в момент, когда / указывает на элемент, больший точки отсчета, а г, соответственно, на элемент, меньший точки отсчета. Последний обмен с точкой отсчета означает окончание стадии деления

return;

Object pivot = S.atRank(rightBound).element(); int leftlndex = leftBound; // сканировать вправо int rightlndex ~ rightBound – 1; // сканировать влево while (leftlndex <= rightlndex) {

// при сканировании вправо найти элемент больше точки отсчета while ( (leftlndex <= rightlndex) &&

c.isLessThanOrEqualTo(S.atRank(leftlndex).element(), pivot)) leftlndex++;

// при сканировании влево найти элемент меньше точки отсчета

while ( (rightlndex >= leftlndex) &&

c.isGreaterThanOrEqualTo(S.atRank(rightlndex).element(), pivot)) rightlndex —; if (leftlndex < rightlndex) // оба элемента найдены

S.swapElements(S.atRank(leftlndex), S.atRank(rightlndex)); } // цикл продолжается до тех пор, пока индексы не пересекутся // расположить точку отсчета, поменяв ее местами с элементом в leftlndex S.swapElements(S.atRank(leftlndex), S.atRank(rightBound)); // точка отсчета в leftlndex, выполнить рекурсивный проход в обе // стороны от нее

quickSortStep(S, с, leftBound, leftlndex – 1);

quickSortStep(S, с, leftlndex+1, rightBound); } ‘

Фрагмент кода 10.7. Java-реализация внутренней быстрой сортировки. Здесь последовательность реализована массивом и содержит уникальные элементы

К сожалению, приведенная выше реализация не является полностью внутренней сортировкой, так как не выполняется требование постоянного объема дополнительной памяти. И действительно, дополнительное место для создания подпоследовательностей не используется, и только для локальных переменных (/ и г) задействован постоянный объем памяти. На что же уходит дополнительное место? На рекурсию. В п. 4.1.3 обоснована необходимость дополнительного пространства для стека, пропорционального глубине рекуррентного дерева при быстрой сортировке, что составляет по крайней мере log п и максимум п — 1. Чтобы быстрая сортировка действительно выполнялась внутри некоторого постоянного объема памяти, она должна быть реализована не рекурсивно (без применения стека). Ключевым элементом такой реализации является способ определения границ «текущих» левой и правой подпоследовательностей. Однако такая схема не очень сложна, поэтому ее подробности оставлены для самостоятельного решения в упражнении 3-10.5.

Время выполнения быстрой сортировки

Проанализировать время выполнения быстрой сортировки можно с помощью методики, примененной при анализе времени сортировки слиянием в п. 10.1.1, то есть определением затрат времени на каждый ‘узел дерева быстрой сортировки Г (рис. 10.10, 10.11, 10.12), а затем суммированием времени выполнения для всех узлов.

Реализовать стадии деления и слияния в быстрой сортировке за линейное время (пропорционально 0(п)) несложно. То есть затраты времени на узел v дерева Г пропорциональны входному размеру s(v) узла v, соответствующему размеру обрабатываемой в этом узле последовательности. Поскольку подпоследовательность Е содержит по крайней мере один элемент (точку отсчета, которая становится корнем дерева), сумма исходных размеров дочерних элементов узла v составит максимум s(v) – 1.

Пусть Sj означает сумму исходных размеров узлов на глубине / дерева Т. Очевидно, что sq = п, поскольку корень г дерева Т ассоциируется со всей последовательностью. Значение s\< п – I, поскольку корень не входит в последовательности дочерних элементов корня г. Перейдем к ^ Если обе подпоследовательности дочерних элементов корня г имеют не равный нулю размер, то s2 = п – 3. Если же одна из этих последовательностей имеет нулевой размер, то размер второй подпоследовательности составит п – 1, и, следовательно, s2 = п – 2. Таким образом, получим, что s2< п-2. Продолжая эту цепочку, можно заключить, что st< п- /. Как отмечалось в разделе 10.3, высота дерева Г составляет в наихудшем случае п – 1. Следовательно, максимальное время выполнения быстрой сортировки есть

Согласно утверждению 3.4,есть. Таким образом, наихудшее

время выполнения быстрой сортировки составит. Исходя из названия, сортировка должна выполняться быстро. Однако указанные выше квадратичные границы означают, что в исключительных случаях сортировка замедляется. Парадокс, но это происходит в случаях, когда сортировка должна быть простой — в уже упорядоченной последовательности. Более того, можно показать, что быстрая сортировка работает очень медленно именно в случае «практически» упорядоченной последовательности.

Быстрая сортировка последовательности из уникальных элементов выполняется наиболее эффективно, если подпоследовательности L и G приблизительно одного размера. В этом случае сохраняется по одной точке отсчета в каждом составном узле и осуществляются два одинаковых вызова для их дочерних элементов. Таким образом, одна точка отсчета сохраняется в корне, две — на первом уровне, 22 — на втором и так далее. В результате получаем

s0 =п

s{ = п -1

S 2 = п-(\ + 2)=п-3

J

s, =л-(1 + 2 + 22 +…+ 2,‘-,) = л-(2′ -1)

Следовательно, в лучшем случае Т имеет высоту 0(log п) и время выполнения быстрой сортировки 0(п log п). Обоснование данного утверждения оставлено для упражнения 3-10.10.

Неформальная интуиция позволяет предположить, что точка отсчета делит исходную последовательность на две почти равные части. Это позволяет считать, что среднее время выполнения быстрой сортировки будет соответствовать лучшему случаю, то есть 0(п log п). В следующем разделе показано, что применение принципа рандомизации позволяет быстрой сортировке выполняться именно так, как описано выше.

\

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.