Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3].

Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой - больше, либо равны p. Разделение завершено.

Общий алгоритм

Псевдокод.

quickSort ( массив a, верхняя граница N ) {

Выбрать опорный элемент p - середину массива

Разделить массив по этому элементу

Если подмассив слева от p содержит более одного элемента,

вызвать quickSort для него.

Если подмассив справа от p содержит более одного элемента,

вызвать quickSort для него.

}

Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n²) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге... Вообще говоря, малореальная ситуация.

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

Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.

Модификации кода и метода

1. Из-за рекурсии и других "накладных расходов" Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%.

Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из <=CUTOFF элементов, отсортированные друг относительно друга. Близкие элементы имеют близкие позиции, поэтому, аналогично сортировке Шелла, вызывается insertSort(), которая доводит процесс до конца.

2. В случае явной рекурсии, как в программе выше, в стеке сохраняются не только границы подмассивов, но и ряд совершенно ненужных параметров, таких как локальные переменные. Если эмулировать стек программно, его размер можно уменьшить в несколько раз.

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

4. Пусть входные последовательности очень плохи для алгоритма. Например, их специально подбирают, чтобы средний элемент оказывался каждый раз минимумом. Как сделать QuickSort устойчивой к такому "саботажу" ? Очень просто - выбирать в качестве опорного случайный элемент входного массива. Тогда любые неприятные закономерности во входном потоке будут нейтрализованы. Другой вариант - переставить перед сортировкой элементы массива случайным образом.

5. Быструю сортировку можно использовать и для двусвязных списков. Единственная проблема при этом - отсутствие непосредственного доступа к случайному элементу. Так что в качестве опорного приходится выбирать первый элемент, и либо надеяться на хорошие исходные данные, либо случайным образом переставить элементы перед сортировкой.

Рассмотрим наихудший случай, когда случайно выбираемые опорные элементы оказались очень плохими(близкими к экстремумам). Вероятность этого чрезвычайно мала, уже при n = 1024 она меньше 2^-50, так что интерес скорее теоретический, нежели практический. Однако, поведение "быстрой сортировки" является "эталоном" для аналогично реализованных алгоритмов типа "разделяй-и-властвуй". Не везде можно свести вероятность худшего случая практически к нулю, поэтому такая ситуация заслуживает изучения.

Пусть, для определенности, каждый раз выбирается наименьший элемент a_min . Тогда процедура разделения переместит этот элемент в начало массива и на следующий уровень рекурсии отправятся две части: одна из единственного элемента a_min, другая содержит остальные n-1 элемента массива. Затем процесс повторится для части из (n-1) элементов.. И так далее..
При использовании рекурсивного кода, подобного написанному выше, это будет означать n вложенных рекурсивных вызовов функции quickSort.
Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям.

Для исключения подобной ситуации можно заменить рекурсию на итерации, реализовав стек на основе массива. Процедура разделения будет выполняться в виде цикла.
Каждый раз, когда массив делится на две части, в стек будет направляться запрос на сортировку большей из них, а меньшая будет обрабатываться на следующей итерации. Запросы будут выбираться из стека по мере освобождения процедуры разделения от текущих задач. Сортировка заканчивает свою работу, когда запросы кончаются.

Псевдокод.

Итеративная QuickSort (массив a, размер size) {

Положить в стек запрос на сортировку массива от 0 до size-1.

do {

Взять границы lb и ub текущего массива из стека.

do {

1. Произвести операцию разделения над текущим массивом a[lb..ub].

2. Отправить границы большей из получившихся частей в стек.

3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.

} пока меньшая часть состоит из двух или более элементов

} пока в стеке есть запросы

}

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Сортировка слиянием

Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели quickSort. А именно, вместо разделения по опорному элементу массив просто делится пополам.

Функция merge на месте двух упорядоченных массивов a[lb]...a[split] и a[split+1]...a[ub] создает единый упорядоченный массив a[lb]...a[ub].

Пример работы алгоритма на массиве 3 7 8 2 4 6 1 5..

Рекурсивный алгоритм обходит получившееся дерево слияния в прямом порядке. Каждый уровень представляет собой проход сортировки слияния - операцию, полностью переписывающую массив.

Обратим внимание, что деление происходит до массива из единственного элемента. Такой массив можно считать упорядоченным, а значит, задача сводится к написанию функции слияния merge.

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

merge ( упорядоченные последовательности A, B , буфер C ) {

пока A и B непусты {

cравнить первые элементы A и B

переместить наименьший в буфер

}

если в одной из последовательностей еще есть элементы

дописать их в конец буфера, сохраняя имеющийся порядок

}

Пример работы на последовательностях 2 3 6 7 и 1 4 5

Результатом является упорядоченная последовательность, находящаяся в буфере. Каждая операция слияния требует n пересылок и n сравнений, где n - общее число элементов, так что время слияния: Theta(n).

Оценим быстродействие алгоритма: время работы определяется рекурсивной формулой T(n) = 2T(n/2) + Theta(n).

Ее решение: T(n) = n log n - результат весьма неплох, учитывая отсутствие "худшего случая". Однако, несмотря на хорошее общее быстродействие, у сортировки слиянием есть и серьезный минус: она требует Theta(n) памяти.

Хорошо запрограммированная внутренняя сортировка слиянием работает немного быстрее пирамидальной, но медленнее быстрой, при этом требуя много памяти под буфер. Поэтому mergeSort используют для упорядочения массивов, лишь если требуется устойчивость метода(которой нет ни у быстрой, ни у пирамидальной сортировок).

Сортировка слиянием является одним из наиболее эффективных методов для односвязных списков и файлов, когда есть лишь последовательный доступ к элементам.

Задачи

Задача 1.

Предположим, что имеется некоторый кусок ленты, разделенный на кадры. Кадры занумерованы с двух сторон. Полоска ленты склеена в лист Мебиуса. Необходимо составить алгоритм упорядочения этой последовательности, предположив, что соседние кадры можно переставлять, (естественно, в упорядоченной последовательности будет один "скачок" от минимального элемента к максимальному). Следует учесть, что при перестановки кадров переставляются числа с обеих сторон кадров. Пример:

Есть 2 кадра

А₁, В₁ - одна сторона кадров,

А₂, В₂ - другая.

Пусть А₁=1, А₂=2, В₁=7, В₂=3. Тогда после перестановки содержащего А В будет А₁=7, А₂=3, В₁=1, В₂=2).

Всегда ли такое упорядочение возможно?

Задача 2.

Имеется N камней веса А₁,А₂,...,А_N.

Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.

Задача 3.

Условие задачи 2, только веса куч отличаются не более, чем в 1,5 раза.

Задача 4.

Имеется N человек и целые числа А₁, ..., A_N; человека i необходимо познакомить с А_i людьми. Можно ли это сделать?

Задача 5.

Условие задачи 4. Кого с кем знакомить, чтобы это сделать?

Задача 6.

Даны две целочисленных таблицы А [1:10] и В[1:15]. Разработать алгоритм и написать программу, которая проверяет, являются ли эти таблицы похожими. Две таблицы называются похожими, если совпадают множества чисел, встречающихся в этих таблицах.

Задача 7.

Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв).

Задача 8.

Задано семейство множеств букв. Найти такое k, для которого можно построить множество, состоящее из k букв, причем каждая из них принадлежит ровно k множествам заданного семейства.

Задача 9.

На прямой окрасили N отрезков.Известны координата L[I] левого конца отрезка и координата R[I] правого конца I-го отрезка для I=1, ..., N. Найти сумму длин всех окрашенных частей прямой.

Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени.

МОДИФИКАЦИЯ. На окружности окрасили N дуг. Известны угловая координата L[I] начала и R[I] конца I-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?

Задача 10.

Имеется 2*N чисел. Известно что их можно разбить на пары таким образом, что произведения чисел в парах равны. Сделать разбиение, если числа

а) натуральные;

б) целые.

Задача 11.

Имеются числа А₁,А₂,...,А_N и B₁,B₂,...,B_N. Составить из них N пар (А_i, B_j) таким образом, чтобы сумма произведений пар была максимальна (минимальна). Каждое A_i и B_j в парах встречаются ровно по одному разу.

Задача 12.

В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения - время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.

Задача 13.

Упорядочить по невозрастанию 5 чисел за 7 операций сравнения.

Задача 14.

Задаются число n>1 - размерность пространства и pазмеpы М n-мерных параллелепипедов (a_i1 , ..., a_in), i=1,...,M.

Паpаллелепипед может располагаться в пространстве любым из способов, при которых его ребра параллельны осям координат. Найти максимальную последовательность вкладываемых друг в друге паpаллелепипедов.

Задача 15.

Пусть A - множество из N натуральных чисел. Ваша программа должна определить, существует ли по крайней мере одно подмножество B множества A, имеющие cледующее свойство (*) для любых X,Y,Z из B, X<>Y<>Z<>X,

X+Y+Z <= {t: t из B\{X,Y,Z}},

тут B\{X,Y,Z} означает 'множество B без элементов X,Y и Z'.

В случае положительного ответа программа должна найти подмножество B, удовлетворяющее условию (*) и состоящее из максимально возможного числа элементов.

Задача 16.

Дано положительное целое число К и К целых чисел А(1),...,А(К). Вычислить

а) наибольшее,

b) наименьшее,

c) наиболее близкое к нулю,

d) наиболее близкое к заданному числу Р возможное значение суммы

S(М,N)=А(М)+А(М+1)+...+А(N-1)+А(N),

где 1<=М<=N<=К.

Примечание. Число К столь велико, что числа А(1),А(2), ..., А(К) занимают примерно одну пятую памяти, отводимой для хранения данных, а на выполнение К² даже простейших операций не хватает времени.

Задача 17.

Даны целые M и N и вектор действительных чисел X[1..N]. Найти целое число i (1<=i<=N-M), для которого сумма x[i]+...+x[i+M] ближе всего к нулю.

Задача 18.

Есть два отсортированных в порядке неубывания массива A[1,N] и B[1,M]. Получить отсортированный по неубыванию массив C[1,N+M], состоящий из элементов массивов A и B ("слить" вместе массивы A и B).

Задача 19.

Дан массив X[1..N]. Необходимо циклически сдвинуть его на k элементов вправо (т.е. элемент X[i] после сдвига должен стоять на месте X[i+k]; тут мы считаем что за X[N] следует X[1]). Разрешается использовать только несколько дополнительных слов памяти (Дополнительного массива заводить нельзя!).

Задача 20.

Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а₁, ...а_n , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.

Контрольные вопросы

1. Каким образом производится пирамидальная сортировка? Каковы ограничения для данного алгоритма? Сколько операций потребуется для сортировки данным методом в худшем случае? В соеднем?

2. Каким образом производится быстрая сортировка? Каковы ограничения для данного алгоритма? Сколько операций потребуется для сортировки данным методом в худшем случае? В соеднем?

3. Каким образом производится сортировка слиянием? Каковы ограничения для данного алгоритма? Сколько операций потребуется для сортировки данным методом в худшем случае? В соеднем?