Пошук, сортування та поняття складності у програмуванні, Детальна інформація

Пошук, сортування та поняття складності у програмуванні
Тип документу: Реферат
Сторінок: 14
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 43.1
Скачувань: 910
mrg(A, l, m-l+1, r-m, B);

for k:=l to r do A[k]:=B[k];

end;

Ff•

Ця процедура набагато коротше нерекурсивної процедури Merges, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції".

Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. Розглянемо два алгоритми, позбавлені цього недоліку.

4.2. Піраміда, вона ж дерево

Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку – перший елемент, у другому – елементи з індексами 2, 3, у наступному – 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним. Наприклад, за кількості елементів n=12 маємо таку піраміду індексів:

1

2 3

4 5 6 7

8 9 10 11 12

Елементи цієї піраміди будемо називати вузлами.

Між вузлами проведемо стрілки: від 1 – до 2 та 3, від 2 – до 4 та 5, від 3 – до 6 та 7 тощо, тобто від кожного вузла k до 2k та 2k+1, де k
Піраміду можна розглядати як дерево, гілки якого – стрілки від батьків до синів. Вершина піраміди називається коренем дерева.

Припустимо тепер, що значення елементів масиву розташовано так, що значення кожного елемента-батька не менше значень його синів:

A[1] \xF0B3 A[2] та A[1] \xF0B3 A[3], A[2] \xF0B3 A[4] та A[2] \xF0B3 A[5] тощо.

Отже, за кожного k=1, 2, … , n div 2

A[k] \xF0B3 A[2*k] та A[k] \xF0B3 A[2*k+1] (17.2)

(за парного n елемент A[n div 2] має лише одного сина A[n]). Наприклад,

30

12 30

12 5 29 2

11 10 3 2 28 27

Цій піраміді відповідає послідовне розташування <30, 12, 30, 12, 5, 29, 2, 11, 10, 3, 2, 28, 27>.

Очевидно, що кожний елемент має значення, найбільше в тій піраміді, де він є вершиною. Наприклад, A[2] має значення, найбільше серед елементів із індексами 2, 4, 5, 8, 9, 10, 11. Зокрема, A[1] має значення, найбільше серед усіх елементів.

Якщо поміняти місцями значення A[1] і A[n], то елемент A[n] матиме найбільше значення. Про нього "можна забути" та зосередитися на сортуванні A[1], A[2], ... , A[n-1]. Зрозуміло, що умова A[1]\xF0B3 A[2], A[1]\xF0B3 A[3] після обміну може виявитися порушеною. Для її відновлення треба обміняти місцями значення A[1] та того з A[2], A[3], чиє значення максимальне. Нехай це буде A[3]. В останньому прикладі після обміну значень A[1] і A[12] на вершині піраміди значення 27, і 27<30, тобто A[1]
Після відновлення умови (17.2) можна буде обміняти значення першого елемента з передостаннім, "забути" про нього, знову відновити умову, знову загнати перше значення в кінець тощо.

Нехай процедура bld(A, n) задає початкову перестановку значень масиву таким чином, що виконується умова (17.2), а процедура reorg(A, i, k) – її відновлення у частині масиву A[i], … , A[k]. Тоді за дії означень (17.1) сортування задається процедурою Treesort:

The online video editor trusted by teams to make professional video in minutes