Д.Кнут. Искусство программирования для ЭВМ. тт 1-3. Москва. Мир. 1996-1998 Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999. Препарата Ф.,
Шеймос М. Вычислительная геометрия. Москва. Мир. 1989 |
Определение. Медианой множества А = {a1 ,…, aN }
называется элемент с индексом (N+1)/2 в
отсортированном по возрастанию множестве А.
Пусть, для определенности, мы сортируем массив вещественных чисел. Идея алгоритма заключается в следующем. Выберем некоторое число, желательно близкое, в каком-то смысле, к медиане сортируемого множества. Разобьем наше множество на две половины – в одной (левой половине) должны быть элементы меньше или равные выбранного элемента, а в другой (в правой половине) – больше или равные. Из построения этих подмножеств следует, что их расположение совпадает с их расположением в отсортированном множестве чисел (расположение – в смысле множеств), т.е. после сортировки элементы из этих подмножеств останутся на месте этих же подмножеств. Т.о., применив рекурсивно эту же процедуру для каждого из подмножеств, мы, в конечном итоге, получим отсортированное множество.
Для реализации этой идеи рассмотрим алгоритм, который не предполагает хранения медианы в отдельной ячейке памяти. В процессе работы алгоритма мы будем следить за тем, в какой ячейке памяти располагается элемент исходного множества, который мы выбрали в качестве медианы. Подобная реализация в реальности чуть более медленная, но доказательство работы алгоритма намного проще, чем в случае хранения медианы в отдельной ячейке.
В следующей реализации в комментариях показаны соотношения на значения элементов, которые выполняются после каждого шага алгоритма. Эти соотношения доказывают, что каждый раз массив разбивается на части, левая из которых не превосходит медианы, а правая – не меньше медианы. Здесь для простоты множество элементов { A s , A s+1 , … , A t } будем обозначать {s,t}. Медиану будем обозначать M.
QuickSort(A,p,q)
Если q-p < 1 то ВЫЙТИ
Вечный цикл
i=p; j=q; // пусть M=A j
//цикл 1:
Пока Ai < A j : i + +;
//{p,i-1}<=M<={j,q}, Ai>=M
поменять
местами A i и A j ;//x -> Ai
//{p,i}<=M<={j,q}
j --;
//{p,i}<=M<={j+1,q}
Если i >= j то
//либо i==j то
{p, j}<=M<={ j+1,q}
// либо i==j+1 то
M== Aj+1 => {p, j}<=M<={ j+1,q}
{ QuickSort(A, p, j ); QuickSort(A,
j+1, q );ВЫЙТИ }
//цикл 2:
Пока A j > Ai : j - -;
//{p,i}<=M<={j+1,q}, A j<=M
поменять местами
A i и A j ;//x -> A j
//{p,i}<=M<={j,q}
i + +;
//{p,i-1}<=M<={j,q}
Если i >=
j то
//либо i==j то M== Aj => {p, j}<=M<={ j+1,q}
// либо i==j+1 то {p, j}<=M<={ j+1,q}
{ QuickSort(A, p, j ); QuickSort(A, j+1, q
);ВЫЙТИ }
Конец
вечного цикла
В силу построения
алгоритма j не может стать
меньше 0 и не может быть больше или равным q, поэтому гарантируется, что мы не попадем в
бесконечную рекурсию и границы
рассмотрения массива корректны.
Отметим, что после первого цикла также имеем:
Если i >= j то
//либо i==j то
{p, i}<=M<={ i+1,q}
// либо i==j+1 то M== Aj+1
=> {p, i}<=M<={ i+1,q}
т.е. рекурсию
можно было бы организовать в виде:
{
QuickSort(A, p, i ); QuickSort(A, i+1, q );ВЫЙТИ }
но в этом случае мы можем попасть в бесконечную рекурсию, т.к. в цикле i может дойти
вплоть до q.
После второго цикла также имеем:
Если
i >= j то
//либо i==j то {p, i-1}<=M<={ i,q}
// либо i==j+1 то {p, i-1}<=M<={ i,q}
т.е. рекурсию
можно было бы организовать в виде:
{
QuickSort(A, p, i-1 ); QuickSort(A, i, q );ВЫЙТИ }
В этом случае i не может стать меньше 1 и не может быть больше
q, поэтому такой
вариант алгоритма также возможен.
--------------------------------------------------------------------------------
В более стандартной реализацией основной идеи данного алгоритма выбирается произвольный элемент x сортируемого множества в качестве среднего элемента и помещается в отдельную ячейку памяти. Далее, один шаг алгоритма заключается в следующем. Мы двигаемся слева направо, пока элементы множества меньше x. Затем мы движемся справа налево, пока элементы множества больше x. Если мы еще не встретились, то следует поменять местами элементы, на которых мы стоим при движении в каждую сторону и повторить шаг алгоритма. Если же мы встретились, то алгоритм вызывается для каждой из полученных половин множества.
QuickSort(A,p,q)
Если q-p < 1 то ВЫЙТИ
Вечный цикл
i=p; j=q; x=Ai
Пока A i < x :
i + +;//{p,i-1}<=x, Ai >=x
Пока A j > x :
j - -;//{j+1,q}>=x, Aj <=x
Если
i
< j то
поменять местами
A i и A j ; //{p,i}<=x, {j,q}>=x
иначе
{
//либо i==j то
Ai
==x =>
{p,j}<=x, {j+1,q}>=x
//либо i==j+1 то
{p,j}<=x, {j+1,q}>=x
QuickSort(A, p, j ); QuickSort(A,
j+1, q );ВЫЙТИ
}
i + +; j - -;//{p,i-1}<=x, {j+1,q}>=x
Конец вечного цикла
Замечание 1. При работе алгоритм индексы массива i и j никогда не выйдут за его границы p и q.
Замечание 2. В алгоритме никогда не произойдет вечной рекурсии, т.е. при рекурсивном вызове
p £ j < q
Замечание 3. Алгоритм гарантирует корректное разбиение массива, т.е. после разбиения массива выполняются соотношения
Ak £ x для всех k: p £
k £ j
Al ³ x для всех k: j+1 £ k £ qj
Тонкость алгоритма характеризует следующее наблюдение. Давайте попробуем ``обезопасить алгоритм’’ и включим обеспечение условия i £ j в циклы алгоритма Пока… . Т.е. приведем алгоритм к следующему виду:
QuickSort*(A,p,q)
Если q-p £ 1 то ВЫЙТИ
Вечный цикл
i=p; j=q; x=Ai
Пока A i < x и
i < j : i + +;
Пока A j > x и
i < j : j - -;
Если
i
< j то
поменять
местами A i и A j ;
иначе
{ QuickSort(A, p, j ); QuickSort(A, j+1, q
);ВЫЙТИ }
i + +; j - -;
Конец
вечного цикла
Алгоритм QuickSort* оказывается неверным !!! Это легко увидеть на простейшем примере: {3,4,2,5}.
Доказательство корректности работы алгоритма сводится к доказательству Замечаний 1-3 для каждого тела вечного цикла алгоритма.
Рассмотрим два принципиально разных случая.
1. Случай Ap=min{ Ap , Ap+1 , ..., Aq }. Все остальные элементы массива больше Ap.
В конце первого выполнения тела вечного цикла алгоритма i=p, j=p. Все элементы в первой половине множества (она, в данном случае, состоит из одного элемента) оказываются меньше элементов из второй половины. Массив разбивается на половины размерами 1:N-1, где N=q-p+1 – количество элементов в массиве.
2. Все остальные случаи.
Доказательство Замечания 1. При работе алгоритм индексы массива i и j никогда не выйдут за его границы p и q.
Выход за границы массива, потенциально, может произойти только в результате выполнения циклов Пока… или при выполнении операций i + +; j - -; в конце тела вечного цикла алгоритма.
Изначально на первом месте массива стоит Ap = x. В конце выполнения первого тела вечного цикла алгоритма Ap может поменяться местами с элементом меньше либо равным x и в дальнейшем элемент Ap не изменится. Т.о. на первом месте массива всегда будет стоять элемент £ x и в процессе выполнения цикла Пока… j не сможет оказаться меньше p. В результате выполнения операций i + +; j - -; выхода за левую границу массива также не может произойти, т.к. если бы это произошло, то это означало бы, что перед этой операцией выполнялось бы j=p. Но в этом случае оказывается неверным соотношение i < j (т.к. i³p ) и, следовательно, попасть в данную точку алгоритма при этих условиях оказывается невозможным.
Разберемся с правой границей. Если в первый момент Aq ³ x, то j сразу же уменьшится на 1 и впоследствии Aq не изменится. Это гарантирует, что в процессе выполнения цикла Пока… i не сможет оказаться больше q. Если же Aq < x, то после циклов Пока… i и j не изменятся и Ap и Aq сразу же поменяются местами. Далее Aq не изменится и i не сможет превысить q. В результате выполнения операций i + +; j - -; выхода за правую границу массива не сможет произойти по причинам аналогичным обсужденным ранее. Замечание доказано.
Доказательство Замечания 2. В алгоритме никогда не произойдет вечной рекурсии, т.е. при рекурсивном вызове
p £ j < q
Первое из требуемых неравенств доказано выше. Второе также легко доказать. Действительно, если при первом входе в тело вечного цикла алгоритма Aq ³ x, то j сразу же уменьшится, и мы получим требуемое. Иначе, при первом выполнении тела вечного цикла алгоритма в циклах Пока… , i и j не изменятся, поэтому после этих циклов i < j и j обязано уменьшится в конце тела цикла. Замечание доказано.
Доказательство Замечания 3. Алгоритм гарантирует
корректное разбиение массива, т.е. после разбиения массива выполняются
соотношения
Ak £ x для
всех k: p £
k £ j
Al ³ x для
всех k: j+1 £
l £ q
Согласно построению алгоритма в конце выполнения тела вечного цикла алгоритма гарантируется, что
Ak £ x для всех k < i
Al ³ x для
всех l > j
Т.о. мы сразу же получаем выполнение второго из неравенств Замечания 3. Первое неравенство оказывается более хитрым (именно оно не выполняется при работе алгоритма QuickSort*). В рассматриваемом случае среди элементов правее первого найдется элемент меньше первого, из чего следует, что после первого выполнения циклов Пока… в тела вечного цикла алгоритма i останется строго меньше j, после чего Ai поменяется местом с Aj и выполнится i + +; j - - . Т.о. элемент со значением x далее останется в правой половине массива (этот факт мы используем далее в доказательстве теоремы о среднем времени работы алгоритма QuickSort).
Если после выполнения циклов Пока.. в некотором теле вечного цикла алгоритма окажется, что i > j, то из приведенных соотношений сразу следует первое неравенство Замечания 3. Случай i < j говорит о незавершенности алгоритма. Осталось рассмотреть случай i = j. Этот вариант может реализоваться только в случае, когда Aj = x, тогда получаем, что Ak £ x для всех k < j и Ak = x для всех k = j. Итого, получаем первое неравенство Замечания 3 (в алгоритме QuickSort* этот случай создается искусственно и поэтому первое неравенство из Замечания 3 остается невыполненным).
¢
Оценим временя работы приведенного алгоритма в худшем случае.
Теорема. Время работы алгоритма QuickSort равно
O(N 2),
где N
– количество элементов в сортируемом массиве.
Доказательство. После каждого разбиения массива на
две части длина самой большой из двух образовавшихся половин оказывается меньше
либо равной длине разбиваемого массива –1. Поэтому на каждой
ветви алгоритма будет не более N узлов (разбиений массива). На
каждом уровне дерева разбиений присутствуют не более N сортируемых элементов, поэтому
время, затрачиваемое на слияние их подмножеств равно O( N ). Итого, суммарное
время работы алгоритма равно O( N
) * N = O( N 2).
Данная оценка достижима на массиве {N,N-1,…,1}.
¢
Оказывается, что число ``неприятных’’ случаев, т.е. таких расположений массивов чисел, при которых время работы алгоритма QuickSort велико, оказывается, относительно, небольшим. Вообще, верна теорема
Теорема. Среднее время работы алгоритма QuickSort равно Q(N log2 N), где N –
количество элементов в сортируемом массиве. Под средним временем подразумевается
среднее время по всем перестановкам любого массива входных данных длины N, состоящего из различных
элементов.
Данная теорема объясняет, в каком смысле данный алгоритм является оптимальным. В то же время, в реальной жизни, часто поток входных данных не является случайным, поэтому в качестве медианы следует брать случайно выбранный элемент. Для этого внесем в алгоритм QuickSort следующее дополнение. Перед присваиванием x=Ai поменяем местами i-ый элемент массива со случайно выбранным элементом среди элементов с индексами от p до q. Назовем получившийся алгоритм QuickSortP. Приведенная теорема верна также и для алгоритма QuickSortP. Докажем ее именно для последнего алгоритма. Будем, кроме того, предполагать, что все элементы входной последовательности различны, или, что то же самое, на входе подается последовательность различных элементов из множества {1,…,N}.
В рассматриваемом случае если x=1, то перед входом в рекурсию алгоритма QuickSort множество разобьется на части размером 1 и N-1. В любом другом случае, как отмечалось выше в доказательстве Замечания 3, элемент x останется в правой половине массива и размер левой половины массива, поэтому, будет равен x-1.
Выпишем рекуррентное соотношение на среднее время работы алгоритма
T(N) =
[ (T( 1 ) +T( N-1 )) + Si=2i£N (T( i-1 ) +T( N-i+1 ))]/N + Q(N) =
= [
(T( 1 ) +T( N-1 )) + Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) =
= [ (T( 1 ) +T( N-1 ) ]/N + [ Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) =
= [
Si=1i<N (T( i ) +T( N-i ))]/N + Q(N)
Предположим, для i<N верно:
T( i
)<a i log i +c
для некоторых a>0, c>0 ,
тогда задача сводится к нахождению таких a>0, c>0 , что для них всегда бы выполнялось соотношение
[ Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) < a N log N +c
Итак
[
Si=1i<N (T( i ) +T( N-i ))]/N < [ Si=1i<N (a i log i +c + a (N-i) log (N-i) +c ))]/N =
= [
Si=1i<N (a i log i +c ))]2/N < a [ Si=1i<N i log i ]2/N +2 c
Оценим сумму из соотношения:
Si=1i<N i log i = Si=1i<N i log N + Si=1i<N i log (i/N) = N 2 log N
/ 2 - Si=1i<N i log (N/i) £
N 2 log N / 2 - Si=1i<N/4 i log (N/i) £
N 2 log N / 2 - Si=1i<N/4 i 2 £
N 2 log N / 2 - N 2/ 8
Т.о. имеем
[
Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) < a (N log N -
N / 4) + 2 c + Q(N) =
= a N log N + c +
(Q(N) + c – a N / 4 )
Осталось взять такое большое a, что (Q(N) + c – a N / 4 )<0, после чего мы получаем требуемое соотношение.
¢
К сожалению, обе приведенные реализации алгоритма QuickSort не являются жизнеспособными. Это связано с тем, что в обоих алгоритмах максимально возможная глубина рекурсии равна N. В этом случае требуется порядка O(N) байт дополнительной памяти, что не фатально, но проблема в том, что эта память будет выделяться в стеке задачи, а стек задачи всегда имеет маленький (относительно) размер. Поэтому, например, в Microsoft Visual Studio мы может ожидать ситуации stack overflow при размерах целочисленного массива порядка 100000 (размер стека здесь по умолчанию равен 1M).
Выходом из положения является следующее решение. Будем рекурсивно решать задачу сортировки только для меньшей половины массива. А большую половину будем сортировать в этой же процедуре. В таком случае глубина погружения в рекурсию не будет превосходить ]log2N[, что является приемлемым.
В реальности для данной реализации требуется внести минимальные добавки в исходный алгоритм быстрой сортировки. Например, алгоритм QuickSort может быть модифицирован следующим образом:
QuickSortR1(A,p,q)
Если q-p < 1 то ВЫЙТИ
Вечный цикл
Метка:
i=p; j=q; x=Ai
Пока A i < x :
i + +;
Пока A j > x :
j - -;
Если
i
< j то
поменять
местами A i и A j ;
иначе
{
if(j-p<q-(j+1))
{
QuickSort(A, p, j );
p=j+1;q=q;goto Метка;
}
иначе
{
QuickSort(A, j+1, q );
p=p;q=j;goto Метка;
}
ВЫЙТИ
}
i + +; j - -;
Конец
вечного цикла
Здесь добавлены:
- метка (может быть заменена еще одним вечным циклом),
- проверка, какая часть массива больше,
- переназначение p,q в каждом случае.
К задачам сортировки могут быть за линейное время сведены следующие классические задачи
Задача 1. Найти
все различные элементы множества {A1,…,AN }, где – Ai , например, целые
или вещественные числа.
Задача 2. Определить,
все ли элементы в множестве A={A1,…,AN } различаются, где – Ai , например, целые или вещественные числа.
Задача 3. Определить,
совпадают ли два множества {A1,…,AN } и {B1,…,BN }, где
Ai , Bi , например, – целые
или вещественные числа.
Т.о., мы
получаем, что для всех трех приведенных задач верхняя оценка времени решения
равна Q (N log N).
Можно задаться вопросом: а можно ли решить эти задачи быстрее? Заметим, что Задача 2 может быть за линейное время сведена к Задаче 1, поэтому если мы докажем, что нижняя оценка времени решения Задачи 2 есть Q(N log N), то тем мы докажем неулучшаемость полученной оценки для Задачи 1.
Задача 2 относится к классу задач о принятии решения. Это значит, что на выходе таких задач выдается всего один бит информации, т.е. ответ `да’ или `нет’. Мы будем рассматривать алгоритмы решения задач о принятии решений, которые сводятся к бинарному дереву принятия решений. Под деревом принятия решений имеется в виду следующее. Пусть на входе нашего алгоритма находится вектор входных данных aÎIR N. Рассмотрим бинарное дерево, в каждой вершине которого вычисляется некоторая функция от вектора a и в зависимости от знака этой функции происходит переход на правую или левую ветвь дерева. Каждая конечная вершина дерева будет называться либо принимающей либо отвергающей, в зависимости от приписанного ей соответствующего атрибута. Достижение принимающей вершины означает выдачу алгоритмом ответа `да’, а отвергающей, соответственно, - `нет’.
Дерево принятия решений называется алгебраическим деревом принятия решений степени n, если функции в вершинах дерева являются многочленами степени не выше n.
Далее мы рассмотрим лишь алгоритмы, представимые в виде алгебраического дерева принятия решений степени 1. Мы будем предполагать, что время вычисления каждой функции в вершине дерева есть Q(1). Приведенная далее теорема верна и для деревьев высшей степени, но для ее доказательства потребуются весьма серьезные факты из теории функций, которые мы здесь привести не сможем.
Введем два определения.
Разделимые
множества. Множества A, B Ì IR N называются разделимыми
(линейно-разделимыми)
если "
aÎ
A, bÎ
B найдется cÎ [a,b], такое что сÏ
A, сÏ
B.
Связное множество. Связным множеством называется такое множество, что при любом его разбиении на два непересекающихся непустых подмножества одно из них содержит точку, предельную для другого. В евклидовом пространстве открытое множество связно тогда и только тогда, когда любые две его точки можно соединить целиком лежащей в нём ломаной.
Теорема. Пусть W Ì IR N – множество точек, на которых решением задачи будет `да’. Пусть #W – количество разделимых связных компонент множества W. Тогда, в рамках алгоритмов, описывающихся алгебраическими деревьями степени 1, время решения задачи есть W(log 2 #W).
Доказательство. Докажем, что количество принимающих вершин дерева принятия решений не меньше #W. Для этого докажем, что все элементы R N, относящиеся к одной принимающей вершине дерева решений находятся внутри одной разделимой связной компоненты W.
Предположим противное: существует принимающая вершина дерева принятия решений, в которую попадает алгоритм при использовании двух различных a,bÎ W , таких что a и b принадлежат различным разделимым связным компонентам Va , Vb Ì W, соответственно. Рассмотрим [a,b]. Линейные функции от N переменных обладают свойством монотонности на отрезке, поэтому все функции, вычисляющиеся в вершинах дерева принятия решений, сохраняют свой знак на [a,b]. Т.о. весь отрезок [a,b] Ì W (т.к. все точки из отрезка обязаны попасть в одно и ту же принимающую вершину). Это противоречит предположению о принадлежности a и b различным разделимым компонентам.
Итак, мы получили, что количество концевых вершин бинарного дерева принятия решений не меньше #W, из чего сразу следует, что высота дерева не меньше [log 2 #W].
¢
Вернемся к решению Задачи 2. Рассмотрим в качестве различных вариантов входных данных задачи все перестановки последовательности {1,2,…,N}. Т.е.
Ap= {p(1), p(2),…, p(N)}, где p – некоторая перестановка.
Докажем, что каждая последовательность Ap принадлежит своей связной разделимой компоненте множества W, на котором решением Задачи 2 будет `да’. Действительно, допустим противное, т.е. пусть две различные последовательности Ap1 и Ap2 принадлежат одной компоненте W. Тогда найдутся 1 £ i, j £ N, такие что (p1(i)- p1(j)) (p2(i)- p2(j))<0, т.е. (p1(i)- p1(j)) и (p2(i)- p2(j)) имеют разные знаки. Но тогда для любой ломаной S, соединяющей точки Ap1 и Ap2 Î IR N , найдется x Î S такая, что xi = xj , что противоречит принадлежности Ap1 и Ap2 одной связной компоненте множества W.
В приведенном доказательстве требует объяснения следующий факт: для двух различных перестановок множества {1,2,…,N} всегда найдутся 1 £ i, j £ N, такие что (p1(i)- p1(j)) и (p2(i)- p2(j)) имеют разные знаки. Пусть для каждой перестановки p: tk – количество чисел p(i) больших p(k) для i>k. Легко увидеть, что p и t однозначно задают друг друга (действительно, для p(i)=N имеем t(i)=0, поэтому если мы найдем такое i, что t(i)=0, то сразу получим, что p(i)=N; далее мы ищем такое i, что t(i)=1, и получаем, что p(i)=N-1, и т.д.). Т.о. для двух различных перестановок p1 и p2 мы получим различные соответствующие t1 и t2 . Выберем i: t1(i) ¹ t2(i). Пусть, например, t1(i) > t2(i), но тогда найдется j>i, такое что p1(j)> p1(i), но p2(j)< p2(i). Получили требуемое.
¢