Главная Полное построение алгоритма [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] 2 S n 8 S 3 7 14 27 2 8 11 8 5 3 ,j 14 27 11 828537 11 378538 14 27 14 27 2 9 7 8 S 3 11 14 27 2 9 7 8 5 3 11 14 27 S 2 7 8 S 3 11 14 27 S 8 7 2 S 3 11 14 27 2(5 5 3 8 7 2 5 9 11 14 27 e S 7 2 3 9 11 14 27 3572 3572 7532 В S 11 14 27 8 9 11 14 27 G 9 11 14 27 @ .25 - 7 8 9 11 2 5 3 7 Б 9 11 14 27 3 S 2 3 14 27 7 8 9 11 14 27 /2 02 2 3 S 7 9 11 14 3 2 3 2 2 Б7 8 91114 27 Б 7 8 91114 27 Зё79П 14.27 Рис. 5.1.6. Полная последовательность шагов при сортировке вершин пирамиды Ге представленной на рис, 5,1,5. няем процедуру шага 3 и переставляем А {i) с большим из элементов Л (20 и Л(2г+1). На рис. 5.1.8 показано, что массив, изображенный на рис. 5.1.7, а, после 15 шагов преобразуется в пирамиду Т, показанную на рис. 5.1.4. ,- 12345 6 78В А 5 3 7 27 9 11 14 2 8 Рис. 5.1.7. Создание дерева из вводимой в произвольном порядке последовательности целых чисел. 1 S S 7 27 S 11 14 2 S Af4}>At8},A(9) . 2 Б 3 7 27 9 11 14 2 S А(3}>А(6)илиА(7) I Перестановка Af3)«A(7) S Б 3 14 27 9 11 7 2 S А{71 конечная « S 3 14 27 9 11 7 2 8 Aj2}>A(4) A(S) Перестановка А(2) - А{4} е 5 27 14 3 9 11 7 2 8 Af41>A(S) Перестановка А(4) - А(9) е Б 27 14 8 9 11 7 2 3 АО] .конечная Евршина 7 6 27 14 8911723 А(11>А(21гаА(3) Перестановка AtD-AP) в 27 Б 14 8 9 11 7 2 3 А{2}>А(4)шАГБ) ,) it ♦ Перестановка A(22«A[S) ® 7 9 14 8 Б 11 7 2 3 АИконЕЧнай вершина О j27 9 14 8 Б 11 7 2 3 СТОП 3 последова рис. 5.1.7., Рис. 5.1.8. Создание пирамиды из последовательности, представленной на Теперь настало время четко сформулировать алгоритм HEAPSORT. Во-первых, сформулируем алгоритм HEAP (ПИРАМИДА), «подпрограмму», используемую алгоритмом HEAPSORT для преобразования линейного массива в пирамиду. Algorithm HEAP. Поставить элемент А (J) на надлежащее ему место в пирамиде с элементами А (1), А (2),. . ., Л (М), МЗ и 1<J<M Шаг 1. [Помещаем A{J) в пирамиду] While 2У+1<Л1 AND(Л(J)< <Л (2J)ORЛ(4<Л(2J+l)) do [Перестановка с A{J)\ If Л (2/)>Л(2Л-1) then set ТЕМРЛ(У); А (J) <~ А {2J); А i2J) TEMP; and J 2J else set TEMP Л (J); A (J) Л(2/+1); Л(2Л-1)ТЕМР; and J<-2J+l fi od. Шаг 2. [Выполняется ли равенство 2/=M?] If 2/=M AND A {J)< <A i2J) then set TEMP Л (/); Л (J) Л (2J); and Л (2J) <- TEMP fi; and RETURN. Algorithm HEAPSORT. Отсортировать (на месте) массив целых чисел Л(1), Л (2), . . ., A{N), N2, в возрастающем порядке. Шаг 0. [Инициализация] Set / ч- N/2 J ; and N. Шаг 1. [еоздание пирамиды] Do through шаг 3 while />1 od. Шаг 2. [Помещаем Л (/) в пирамиду] CALL НЕАР(/, Л, М). Шаг 3. [Новое значение /] Set --1. Шаг 4. [Сортировка] Do through шаг 6 while Ml od; and STOP. Шаг 5. [Перестановка Л (1) <-> Л (М)] Set TEMP Л (1); Л(1)Л(М); Л(УИ)ТЕМР; and УИМ-1. Шаг 6. [Помещаем Л (1) в пирамиду] CALL НЕАР(1, Л, М). Реализации алгоритмов HEAP й HEAPSORT даны на рис. 5.1.9 и 5.1.10. Доказательство правильности алгоритма HEAPSORT довольно длинное и утомительное Интересующемуся читателю советуем заглянуть в книгу [59]. Анализ сложности подпрограммы HEAPSORT относительно прост. Максимальное количество выполнений оператора указано справе от каждого оператора на рис. 5.1.10. Только две величины заслуживают внимания; они помечены HUNJ2 и (Л-1)»Я2, где Я1 и Н2 обозначают число выполнений операторов в подпрограмме HEAP. Величины А, В, С и D (рис. 5.1.9) связаны следующими соотношениями: Л+B<log2<Гlog21, C+D=l. Нужно только объяснить, почему число выполнений оператора 100 ограничено сверху величиной Г logN"]. В худшем случае имеем начальное значение J=l и значениями К являются 2, 4, 8, 16 (т. е. степени 2). Максимальное число выполнений оператора 100 ограничено наименьшим целым k, таким, что 2=+ l>N, т. е. k= f log2(A-1)"]. Поэтому можно заметить, что в худшем случае подпрограмма HEAP вьшолняет не больше, чем 2N[ (UlogN]+6)+nN+3, или 22Л Г bgaA 1 +23N+3, операторов. [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.002 |