Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [ 71 ] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [ 71 ] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0016