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

[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