довательность, чтобы ее сортировать обычным способом. Для этой цели пользуемся сортировкой простыми включениями (SIS).

Algorithm QUICKSORT. Нужно отсортировать последовательность N ключей А (1), А (2), . . ., А (N), N2, в порядке возрастания, оставив ее на том же месте. Подпоследовательности, длина которых меньше М, сортируются методом сортировки простыми включениями. Алгоритм использует стек (ЬЕРТ(Д), RIGHT (/Q), который содержит индексы крайних левого и правого элементов подпоследовательностей, подлежащих сортировке. Переменная К - число элементов на стеке.

1 2 3 4 S е 7 8 9 10 11 12 13 14 15 16 СтеК

1 (04 OS 16 06 02 24) 38 (67 Б6 76 SS 48 79 70 46 47) (8, IB)

2 02 04 (8,16)

3 04 OS (8,16)

4 (02 04 16 06 08 24) (8,16) e 08 16 (8,16)

6 (08 06) 16 (241 (6,16)

7 02 04 06 08 16 24 38 (57 55 76 Б8 48 79 70 45 47) (8,16)

8 47 57

9 Б7 76

10 45 S7

11 S7 58

12 48 57

13 {47 Б6 45 48) 57 (79 70 58 76) (13,16)

14 AS 47 (13,16)

15 47 Б6 (13,16)

16 {45) 47 (56 48) 110,11)(13,16)

17 AB 47 48 56 S7 (79 70 Б8 76) (13,16)

18 76 79

19 (76 70 58) 79 (13,15)

20 AS 47 48 56 S7 58 7G 76 79

Рис. 5.1.2. Завершение работы алгоритма QUICKSORT при сортировке последовательности, представленной на рис. 5.1.1.

Шаг 1.

Шаг 0. [Инициализация стека] Set /Сч-1; LEFT(/0-«-l; and RIGHT Kh-N.

Цикл] While К>0 do through шаг 12 od; and STOP. Шаг 2. [Выталкивание из стека] Set L-<-LEFT(/0; i?-<-RIGHT(/0; and KK-l.

Шаг 3. [Сортировка длинной последовательности] While R-L>M do through шаг 11 od. Шаг 4. [Инициализация] Set /<-/.; J<-R; and МЮч-Л (/). Шаг 5, [Сравнение MID : A (J)] While МШ<Л (J) do set J<-J-\ od.

Шаг 6. [Прохождение завершено?] If J</ then set A (/)-<-MID;

and go to шаг 11 fi. Шаг 7. [Обмен] Set Л(/)ч-Л(/); A(J}<-MID; and /ч-/+1. Шаг 8. [Сравнение A (I) : MID] While A (/)<MID do set /-t-

ч-/+1 od.

Шаг 9. [Прохождение завершено?] If /1 then set /<-/; and

goto шаг 11 fi. Шаг 10. [Обмен] Set Л(/)ч-Л(/); JW-1; and goto шаг 5. Чиаг 11. [Магазин] Set К<-К+\; if R-II-L then set LEFT(/C)4-/+1; RIGHT (K)R; and RI-l. else set LEFT {K)-<-L; RIGHT {КУ<-1-1; and LZ+l fi.

Шаг 12. [Начало включения] For /--L+l to R do through шаг 15 od.

Шаг 13. [Берется след\ющий ключ] Set B<-A{J); and /ч-/-1. Шаг 14. [Сравнение В" я А {!)] While В<А (/) AND />L do

set Л(/+1)ч-Л(/); and /ч-/-1 od. Шаг 15. [Включение] Set Л(/+1)ч-£.

Перед тем как обсуждать сложность алгоритма QUICKSORT, рассмотрим доказательство его правильности. Этот алгоритм демонстрирует еще один пример, где доказательство можно проводить по индукции. Предположение индукции заключается в том, что QUICKSORT правильно сортирует все последовательности из N-1 элементов. Пусть Л(1), А (2), . . ., A(N) - произвольная последовательность из N элементов. Если следующие три условия выполнены после первого прохождения через последовательность (шаг 11), то из предположения индукции немедленно вытекает, что QUICKSORT правильно отсортирует подпоследовательности (1, /-1) и (/+1, N).

1. QUICKSORT правильно устанавливает окончательное положение Л(1), скажем /.

2. Все элементы, находящиеся слева от /-й позиции, меньше, чем А{1).

3. Все элементы, находящиеся справа от /-й позиции, больше, чем А{1).

Но все три условия следуют из того факта, что QUICKSORT срав-ниваег каждый элемент последовательности А (2), . . ., A{N) с А (1)

при первом прохождении, производя все необходимые обмены для того, чтобы поставить все элементы, меньшие А (1), слева, а все элементы, большие справа.

Чтобы оценить эффективность алгоритма, положим Q(AA) равным среднему числу шагов, необходимых для сортировки N элементов. Предположим также, что М = 1, т. е. что нельзя добиться ускорения, применяя сортировку простыми включениями на коротких подпоследовательностях.

При первом прохождении QUICKSORT проверяет каждый элемент последовательности и выполняет не больше, чем сЛА, шагов, где с - некоторая константа. После этого остается отсортировать две подпоследовательности, длины которых равны соответственно /-1 и N-1. Поэтому среднее число шагов, необходимых для сортировки элементов, зависит от среднего числа шагов, требуемых для сортировки /-1 и N-1 элементов, где / изменяется от 1 до N.

Если мы предположим, что все значения I от I рр N могут с равными вероятностями оказаться в окончательной позиции для / в отсортированной последовательности, то

Q(N)cN + ±- [Q(/ -l) + Q(yV /)]. / = 1

Так как эта сумма, очевидно, равна

Q iO)+Q iN-l)+Q{l)+Q (N-2)+...+Q iN-2)+Q (l)+Q iN-l)+Q (0), мы получаем

Q(N)cN + -QiI). (1)

/ = 0

Покажем индукцией по N, что Q{N)KN\nN для N2, где /С=» =2с+26 и b=Q{0)=Q{l). (Последнее означает, что QUICKSORT требует постоянного числа шагов b для сортировки О или 1 элемента.)

Для N=2 имеем Q(2)<2c-f (Q(0)+Q(l))=2c+2&=/C. Поэтому

предположим, что Q{I)KIlnI для 1=2, 3, . . ., N-1, и перепишем (1) в виде

QiN)cN + iQ{0) + Qil)) + К1\п1

1 = 2

QiN)cN + +KnnI . (2)

Теперь, поскольку функция Лп/ вогнута (рис. 5.1.3),

N-1 Л

/1п /< Гх1пл; dx

1 = 2 Ц

< 2 4