QuickSort. Вторая реализация.

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

QuickSort(A,p,q)

Если q-p < 1 то ВЫЙТИ

i=p; j=q; x=A_i

Вечный цикл

Пока A _i < x : i + +;//{p,i-1}<=x, A_i >=x

Пока A _j > x : j - -;//{j+1,q}>=x, A_j <=x

Если i < j то

поменять местами A _i и A _j ; //{p,i}<=x, {j,q}>=x

иначе

{

//либо i==j то A_i ==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. Алгоритм гарантирует корректное разбиение массива, т.е. после разбиения массива выполняются соотношения

A_k £ x для всех k: p £ k £ j

A_l ³ x для всех k: j+1 £ k £ qj

Тонкость алгоритма характеризует следующее наблюдение. Давайте попробуем ``обезопасить алгоритм’’ и включим обеспечение условия i £ j в циклы алгоритма Пока… . Т.е. приведем алгоритм к следующему виду:

QuickSort^*(A,p,q)

Если q-p < 1 то ВЫЙТИ

i=p; j=q; x=A_i

Вечный цикл

Пока 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. Случай A_p=min{ A_p , A_p+1 , ..., A_q }. Все остальные элементы массива больше A_p.

В конце первого выполнения тела вечного цикла алгоритма i=p, j=p. Все элементы в первой половине множества (она, в данном случае, состоит из одного элемента) оказываются меньше элементов из второй половины. Массив разбивается на половины размерами 1:N-1, где N=q-p+1 – количество элементов в массиве.

2. Все остальные случаи.

Доказательство Замечания 1. При работе алгоритм индексы массива i и j никогда не выйдут за его границы p и q.

Выход за границы массива, потенциально, может произойти только в результате выполнения циклов Пока… или при выполнении операций i + +; j - -; в конце тела вечного цикла алгоритма.

Изначально на первом месте массива стоит A_p = x. В конце выполнения первого тела вечного цикла алгоритма A_p может поменяться местами с элементом меньше либо равным x и в дальнейшем элемент A_p не изменится. Т.о. на первом месте массива всегда будет стоять элемент £ x и в процессе выполнения цикла Пока… j не сможет оказаться меньше p. В результате выполнения операций i + +; j - -; выхода за левую границу массива также не может произойти, т.к. если бы это произошло, то это означало бы, что перед этой операцией выполнялось бы j=p. Но в этом случае оказывается неверным соотношение i < j (т.к. i³p ) и, следовательно, попасть в данную точку алгоритма при этих условиях оказывается невозможным.

Разберемся с правой границей. Если в первый момент A_q ³ x, то j сразу же уменьшится на 1 и впоследствии A_q не изменится. Это гарантирует, что в процессе выполнения цикла Пока… i не сможет оказаться больше q. Если же A_q < x, то после циклов Пока… i и j не изменятся и A_p и A_q сразу же поменяются местами. Далее A_q не изменится и i не сможет превысить q. В результате выполнения операций i + +; j - -; выхода за правую границу массива не сможет произойти по причинам аналогичным обсужденным ранее. Замечание доказано.

Доказательство Замечания 2. В алгоритме никогда не произойдет вечной рекурсии, т.е. при рекурсивном вызове

p £ j < q

Первое из требуемых неравенств доказано выше. Второе также легко доказать. Действительно, если при первом входе в тело вечного цикла алгоритма A_q ³ x, то j сразу же уменьшится, и мы получим требуемое. Иначе, при первом выполнении тела вечного цикла алгоритма в циклах Пока… , i и j не изменятся, поэтому после этих циклов i < j и j обязано уменьшится в конце тела цикла. Замечание доказано.

Доказательство Замечания 3. Алгоритм гарантирует корректное разбиение массива, т.е. после разбиения массива выполняются соотношения

A_k £ x для всех k: p £ k £ j

A_l ³ x для всех k: j+1 £ l £ q

Согласно построению алгоритма в конце выполнения тела вечного цикла алгоритма гарантируется, что

A_k £ x для всех k < i

A_l ³ x для всех l > j

Т.о. мы сразу же получаем выполнение второго из неравенств Замечания 3. Первое неравенство оказывается более хитрым (именно оно не выполняется при работе алгоритма QuickSort^*). В рассматриваемом случае среди элементов правее первого найдется элемент меньше первого, из чего следует, что после первого выполнения циклов Пока… в тела вечного цикла алгоритма i останется строго меньше j, после чего A_i поменяется местом с A_j и выполнится i + +; j - - . Т.о. элемент со значением x далее останется в правой половине массива (этот факт мы используем далее в доказательстве теоремы о среднем времени работы алгоритма QuickSort).

Если после выполнения циклов Пока.. в некотором теле вечного цикла алгоритма окажется, что i > j, то из приведенных соотношений сразу следует первое неравенство Замечания 3. Случай i < j говорит о незавершенности алгоритма. Осталось рассмотреть случай i = j. Этот вариант может реализоваться только в случае, когда A_j = x, тогда получаем, что A_k £ x для всех k < j и A_k = x для всех k = j. Итого, получаем первое неравенство Замечания 3 (в алгоритме QuickSort^* этот случай создается искусственно и поэтому первое неравенство из Замечания 3 остается невыполненным).

¢

Оценки времени работы алгоритма.

Оценим временя работы приведенного алгоритма в худшем случае.

Теорема. Время работы алгоритма QuickSort равно O(N ²), где N – количество элементов в сортируемом массиве.

Доказательство. После каждого разбиения массива на две части длина самой большой из двух образовавшихся половин оказывается меньше либо равной длине разбиваемого массива –1. Поэтому на каждой ветви алгоритма будет не более N узлов (разбиений массива). На каждом уровне дерева разбиений присутствуют не более N сортируемых элементов, поэтому время, затрачиваемое на слияние их подмножеств равно O( N ). Итого, суммарное время работы алгоритма равно O( N ) * N = O( N ²).

Данная оценка достижима на массиве {N,N-1,…,1}.

¢

Оказывается, что число ``неприятных’’ случаев, т.е. таких расположений массивов чисел, при которых время работы алгоритма QuickSort велико, оказывается, относительно, небольшим. Вообще, верна теорема

Теорема. Среднее время работы алгоритма QuickSort равно Q(N log₂ N), где N – количество элементов в сортируемом массиве. Под средним временем подразумевается среднее время по всем перестановкам любого массива входных данных длины N, состоящего из различных элементов.

Данная теорема объясняет, в каком смысле данный алгоритм является оптимальным. В то же время, в реальной жизни, часто поток входных данных не является случайным, поэтому в качестве медианы следует брать случайно выбранный элемент. Для этого внесем в алгоритм QuickSort следующее дополнение. Перед присваиванием x=A_i поменяем местами i-ый элемент массива со случайно выбранным элементом среди элементов с индексами от p до q. Назовем получившийся алгоритм QuickSortP. Приведенная теорема верна также и для алгоритма QuickSortP. Докажем ее именно для последнего алгоритма. Будем, кроме того, предполагать, что все элементы входной последовательности различны, или, что то же самое, на входе подается последовательность различных элементов из множества {1,…,N}.

В рассматриваемом случае если x=1, то перед входом в рекурсию алгоритма QuickSort множество разобьется на части размером 1 и N-1. В любом другом случае, как отмечалось выше в доказательстве Замечания 3, элемент x останется в правой половине массива и размер левой половины массива, поэтому, будет равен x-1.

Выпишем рекуррентное соотношение на среднее время работы алгоритма

T(N) = [ (T( 1 ) +T( N-1 )) + S_i=2^i£N (T( i-1 ) +T( N-i+1 ))]/N + Q(N) =

= [ (T( 1 ) +T( N-1 )) + S_i=1^i<N (T( i ) +T( N-i ))]/N + Q(N) =

= [ (T( 1 ) +T( N-1 ) ]/N + [ S_i=1^i<N (T( i ) +T( N-i ))]/N + Q(N) =

= [ S_i=1^i<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 , что для них всегда бы выполнялось соотношение

[ S_i=1^i<N (T( i ) +T( N-i ))]/N + Q(N) < a N log N +c

Итак

[ S_i=1^i<N (T( i ) +T( N-i ))]/N < [ S_i=1^i<N (a i log i +c + a (N-i) log (N-i) +c ))]/N =

= [ S_i=1^i<N (a i log i +c ))]2/N < a [ S_i=1^i<N i log i ]2/N +2 c

Оценим сумму из соотношения:

S_i=1^i<N i log i = S_i=1^i<N i log N + S_i=1^i<N i log (i/N) = N ² log N / 2 - S_i=1^i<N i log (N/i) £ N ² log N / 2 - S_i=1^i<N/4 i log (N/i) £ N ² log N / 2 - S_i=1^i<N/4 i 2 £ N ² log N / 2 - N ²/ 8

Т.о. имеем

[ S_i=1^i<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).

Выходом из положения является следующее решение. Будем рекурсивно решать задачу сортировки только для меньшей половины массива. А большую половину будем сортировать в этой же процедуре. В таком случае глубина погружения в рекурсию не будет превосходить ]log₂N[, что является приемлемым.

В реальности для данной реализации требуется внести минимальные добавки в исходный алгоритм быстрой сортировки. Например, алгоритм QuickSort может быть модифицирован следующим образом:

QuickSortR1(A,p,q)

Если q-p < 1 то ВЫЙТИ

Вечный цикл

Метка:

i=p; j=q; x=A_i

Пока 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 в каждом случае.