Доказательство корректности работы алгоритма.

Доказательство корректности работы алгоритма сводится к доказательству Замечаний 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 остается невыполненным).

¢

---

Дата добавления: 2015-10-30