Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

175

8. Які три основні висновки можна зробити, аналізуючи виконання запитання 7?

9. Як можна визначити, за яку кількість кроків можна підняти най-більший елемент у корінь бінарного дерева?

8. Зобразіть поетапно на власному прикладі алгоритм сортування за допомогою побудови бінарного дерева та підняття найбіль-шого елемента вгору шляхом побудови піраміди.

9. Яка існує залежність між індексами елементів масиву, які є тер-мінальними вершинами у відповідному бінарному дереві?

10. Яка існує залежність між елементами масиву, з яких можна утво-рити піраміду, зберігаючи їх послідовність у масиві?

11. Сформулюйте словесний алгоритм сортування одновимірного масиву методом пірамідального сортування.

12. Запишіть у вигляді фрагмента Pascal-програми алгоритм піра-мідального сортування.

13. Поясніть окремі фрагменти Pascal-програми, наведено! у запи-танні 14, та їх призначення.

14. Якою є оцінка ефективності роботи алгоритму пірамідального сортування? Обґрунтуйте свою відповідь.

Завдання

1. Реалізувати у вигляді програми алгоритм сортування за­дано! послідовності за зростанням методом пірамідального сор­тування.

2. Модифікувати алгоритм у завданні 1 так, щоб сортування відбувалося за спаданиям.

3. Протестувати реалізовані в завданнях 1—2 алгоритми для масиву 15, 4, 10, 8, 6, 9, 16,1, 7, 3, 11,14, 2, 5,12, 13.

4. Проаналізувати покрокове виконання завдання 3 щодо кількості виконуваних дій.

5. Шдібрати власні тести, які доводять переваги й показують недоліки методу пірамідального сортування при п > 100.

6. Зробити письмовий аналіз завдань 3—5.

Швидке сортування

Метод швидкого сортування Quicksort є удосконаленням «бульбашкового» сортування, або методу прямого обміну. Ідея його була запропонована Чарльзом Хоаром у 1962 р. і полягає в тому, що краще спочатку здійснювати обміни на великих від-станях, які потім зменшуються.

Спробуємо дійти до ідеї алгоритму поступово. Спочатку роз-глянемо вже відсортований за спаданиям масив

94, 67, 55, 44, 42, 18, 12, 06.

Неважко помітити, що якщо у відсортованому за спаданиям масиві взяти будь-який елемент а,, де 1 < i < п, то всі елементи

176

зліва від нього будуть більші або рівні за даний, а справа - мен-mi або рівні.

I ще одна цікава закономірність: масив можна відсортувати за спаданиям за [п/2] кроків, помінявши спочатку місцями пер­ший і останній елементи, потім другий і передостанній і т. д.

Скористаємося цими ідеями для довільного масиву а., а₂,..., а_п. Візьмемо будь-який елемент масиву а_к (1 < k < п). Нехай його значениям є х. Такий елемент носить назву осьового, він умов-но ділить весь масив на дві частини. Тепер будемо послідовно зліва шукати елемент а₍ > х, а справа — а.< х. Знайшовши такі елементи, поміняємо їх місцями, оскільки у впорядкованому варіанті даного масиву вони мають розміщуватися саме так. Продовжимо цей процес доти, поки / та j не зустрінуться. У ре­зультат! отримаємо масив, у якому всі елементи будуть поділені на дві частини відносно позиції і = j масиву: зліва від цієї позиції будуть усі елементи, менші за х, а справа - більші.

Використання ідеї' поділу масиву на дві частини при побу-дові алгоритму сортування відносить його до алгоритмів, побу-дованих на принципі «розділяй і володарюй».

Розглянемо приклад уже відомого нам масиву (мал. 71).

44, 55, 12, 42, 94, 06, 18, 67.

Мал. 71

У якості осьового елемента х візьмемо елемент зі значен­иям 42. У результаті двох обмінів (18 ** 44) і (55 ** 06) отри-маемо результат, зображений на малюнку 72.

r)

в)

Мал. 72

Фрагмент програми, який відповідає запропонованому алго­ритму, можна записати так:

177

i:= 1;j :=n; repeat

while a[i]<x do i := i + 1; while x<a[j] doj :=j- 1; if i <= j then begin

| c:=a[i];a[i] :=a[j];a[j] :=c end; i:=i+1;j:=j- 1; until i > j;

Якщо виконати цей алгоритм за малюнком 72, то виявить-ся, що малюнок 72, в не досить точно відтворює положения ін-дексів і та у по завершению циклу. Виправимо цю неточність (мал. 72, г).

Пояснимо малюнок 72, г: після останнього обміну 55 *-» 06 результатом виконання циклу while a[i] < х do i := i + 1 буде i - 4, a, = 42, а циклу while x < a[j] do j := j - 1 буде j = 4, a_y = 42. Фраг­мент алгоритму, який виконується після завершения обох циклів, доводить, що значения параметрів і та ; змінюються: і := і + 1; j :^s j - 1;. Отже, по завершению цього алгоритму і = 5, а j = 3, тобто їх стан такий, як зображено на малюнку 72, г.

Для того щоб відсортувати весь масив, залишилося цю так­тику застосувати до лівої (1 < k < 3) і правої (5 < k < 8) частин отриманого поділу, потім до лівої та правої частин правої час-тини та відповідно до лівої та правої частин лівої частини пер-шого поділу і т. д. Цей процес будемо продовжувати доти, поки кожна частина не буде складатися з одного елемента.

Продовжимо процес, зображений на малюнку 72, представ-ляючи описаний алгоритм двома фазами сортування масиву на кожному кроці поділу підмасиву на дві частини - ліву і праву -таким чином (мал. 73-76). На лівому малюнку виділятимемо темно-сірим кольором ту частину масиву, яку опрацьовувати-мемо за нашим алгоритмом, виділяючи напівжирним шриф­том осьовий елемент, а світло-сірим - елементи, які уже стоять на своїх місцях. На правому малюнку зображатимемо цю час-тину масиву після обміну місцями лівих і правих елементів ви-діленої частини відносно осьового елемента.

х-т

_{т т т т}

і і j і

а) б)

Мал. 73

178

Т Т

т т

і І

б)

а)

Мал. 74

а)

I У

б)

Мал. 75

т т

Т Т і І

а)

б)