Methods_AP_PZ

Практична робота № 5

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

5.1 Теоретичні відомості

Сортування вставками

Основна ідея сортування вставками полягає в тому, що при додаванні нового елементу у вже відсортований список його варто відразу вставляти в потрібне місце замість того, щоб вставляти його в довільне місце, а потім заново сортувати весь список. Сортування вставками вважає перший елемент будь-якого списку відсортованим списком довжини 1. Двохелементний відсортований список створюється додаванням другого елементу вихідного списку в потрібне місце одноелементного списку, що містить перший елемент. Тепер можна вставити третій елемент вихідного списку у відсортований двохелементний список. Цей процес повторюється до тих пір,

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

Приклад 5.1

Наведемо опис цього алгоритму на псевдокоді.

InsertionSort (list, N)

list сортований список елементів

N число елементів у списку for i = 2 to N do

newElement = list [i] location = i-l

while (location> = 1) and (list [location]> newElement) do

/ / Зрушуємо всі елементи, більші за наступний list [location + l] = list [location]

location = location-l end while

list [location +1] = newElement end for

31

Бульбашкове сортування

Алгоритм бульбашкового сортування здійснює декілька проходів по списку. При кожному проході відбувається порівняння сусідніх елементів.

Якщо порядок сусідніх елементів неправильний, то вони міняються місцями.

Кожен прохід починається з початку списку. Спершу порівнюються перший і другий елементи, потім другий і третій, потім третій і четвертий і так далі;

елементи з неправильним порядком в парі переставляються. При виявленні на першому проході найбільшого елемента списку він буде переставлятися з усіма подальшими елементами поки не дійде до кінця списку. Тому при другому проході немає необхідності проводити порівняння з останнім елементом.

При другому проході другий за величиною елемент списку опуститься в другу позицію з кінця. При продовженні процесу на кожному проході принаймні одне з наступних за величиною значень встає на своє місце. При цьому менші значення теж збираються нагорі.

Якщо при якомусь проході не відбулося жодної перестановки елементів,

то всі вони стоять в потрібному порядку, і виконання алгоритму можна припинити. Варто зауважити, що при кожному проході ближче до свого місця просувається відразу декілька елементів, хоча гарантовано займає остаточне положення лише один.

Приклад 5.2

Опишемо алгоритм, що реалізує цей варіант бульбашкового сортування,

за допомогою псевдокоду.

BubbleSort (list, N)

list сортований список елементів

N число елементів у списку numberOfPairs = N swappedElement s = true while swappedElements do

32

numberOfPairs = numberOfPairs-l swappedElements = false

for i = l to numberdfPairs do if list [i]> list [i + l] then

Swap (list [i], list [i +1]) swappedElements = true

end if end for

end while

Сортування Шелла

Сортування Шелла придумав Дональд Л. Шелл. Його незвичайність полягає в тому, що воно розглядає весь список як сукупність перемішаних підсписків. На першому кроці ці підсписки являють собою просто пари елементів. На другому кроці в кожній групі по чотири елементи. При повторенні процесу число елементів в кожному підсписку збільшується, а

число підсписків, відповідно, падає.

Кореневе сортування

При кореневому сортуванні упорядкування списку відбувається без безпосереднього порівняння ключових значень між собою. При цьому створюється набір "стопок", а елементи розподіляються по стопках в залежності від значень ключів. Зібравши значення назад і повторивши всю процедуру для послідовних частин ключа, ми отримуємо відсортований список. Щоб така процедура працювала, розподіл по стопках і подальшу збірку слід виконувати дуже акуратно.

Приклад 5.3

Опишемо алгоритм кореневого сортування за допомогою псевдокоду.

RadixSort (list, N)

list сортований список елементів

33

N число елементів у списку shift = l

for loop = l to keySize do for entry = l to N do

bucketNumber = (list [entry] .key / shift) mod 10 Append (bucket [bucketNumber], list [entry])

end for entry

list = CombineBuckets Про shift = shift * 10

end for loop

Пірамідальне сортування

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

Сортування починається з побудови піраміди. При цьому максимальний елемент списку виявляється в вершині дерева: адже нащадки вершини обов'язково повинні бути менше. Потім корінь записується останнім елементом списку, а піраміда з віддаленим максимальним елементом переформовується. У результаті в корені виявляється другий за величиною елемент, він копіюється в список, і процедура повторюється поки всі елементи не виявляться повернутими в список.

Ось як виглядає відповідний алгоритм:

сконструювати піраміду for i = l to N do

34

скопіювати корінь піраміди в список

переформувати піраміду

end for

5.2 Завдання на практичну роботу

Виконати завдання згідно вказівок викладача.

1.Випишіть стан списку [7, 3, 9, 4, 2, 5, 6, 1, 8] після кожного проходу алгоритму «вставка».

2.Випишіть стан списку [3, 5, 2, 9, 8, 1, 6, 4, 7] після кожного проходу алгоритму «вставка».

3.Відомо, що найгірший випадок відповідає спадаючому списку. Так,

список [10, 9, 8, 7,6, 5, 4,3,2,1] дає максимально можливе число порівнянь на десяти елементах, тобто 45. Знайдіть ще один список з десяти елементів з найгіршою поведінкою. Що можна сказати про вхідному списку з найгіршим поведінкою в разі довільної довжини?

4.При уважному вивченні алгоритму «вставка» видно, що вставка нового елемента заснована на алгоритмі послідовного пошуку. Модифікуйте сортування вставками, застосувавши двійковий пошук місця вставки нового елемента. Замініть стандартний пошук функцією, що повертає значення шуканої позиції.

5.Випишіть результати всіх проходів алгоритму «бульбашка» на списку

[7, 3, 9, 4, 2, 5, 6, 1, 8].

6. Випишіть результати всіх проходів алгоритму «бульбашка» на списку

[3, 5, 2, 9, 8, 1, 6, 4, 7].

7. Ще в одному варіанті бульбашкового сортування запам'ятовується інформація про те, де відбувся останній обмін елементів, і при наступному проході алгоритм не заходить за це місце. Якщо останніми помінялися i-ий і i

+ 1-ий елементи, то при наступному проході алгоритм не порівнює елементи за i-м.

35

а) Напишіть цей варіант бульбашкового сортування.

б) Напишіть короткий доказ того, чому цей варіант бульбашкового сортування дійсно працює.

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

а) Напишіть цей варіант бульбашкового сортування.

б) Напишіть короткий доказ того, чому цей варіант бульбашкового сортування дійсно працює.

9. У третьому варіанті бульбашкового сортування ідеї першого і другого змінених варіантів суміщені. Цей алгоритм рухається по масиву по черзі вперед і назад і додатково вибудовує початок і кінець списку в залежності від місця останньої зміни.

а) Напишіть цей третій варіант бульбашкового сортування.

б) Напишіть короткий доказ того, чому цей варіант бульбашкового сортування дійсно працює.

10. Доведіть строго, що якщо на черговому проході в алгоритмі

«бульбашка» обмінів не відбулося, то елементи списку йдуть в правильному порядку.

11.Випишіть результати всіх проходів алгоритму Шелла з кроками 7, 5, 3 і 1 на списку [16,15,14,13,12,11,10,9, 8, 7,6, 5,4, 3, 2, 1]. Скільки порівнянь було виконано?

12.Випишіть результати всіх проходів алгоритму Шелла з кроками 8, 4,

2 і 1 на списку [16,15,14,13,12,11,10,9, 8, 7, 6, 5,4, 3, 2, 1]. Скільки порівнянь було виконано?

13. Випишіть результати всіх проходів алгоритму Шелла з кроками 5, 2 і 1 на списку [7,3,9,4,2,5,6,1,8]. Скільки порівнянь було виконано?

36

14.Випишіть результати всіх проходів алгоритму Шелла з кроками 5, 2 і

1на списку [3,5,2,9,8,1,6,4,7]. Скільки порівнянь було виконано?

15.Якщо можна розглядати сортування як видалення інверсій. Яке максимальне число інверсій в списку з N елементів можна видалити,

переставивши два несоседніх елементу списку? Наведіть приклад такої перестановки в списку довжини 10.

16. За допомогою алгоритму кореневого сортування відсортуйте список

[1405,975, 23, 9803, 4835, 2082, 7368, 573, 804, 746, 4703, 1421, 4273, 1208,

521, 2050]. Випишіть стопки при кожному проході і стан списку після кожної збірки списку.

17. За допомогою алгоритму кореневого сортування відсортуйте список

[117,383, 4929,144,462,1365,9726,241,1498,82,1234,8427,237, 2349,127,462].

Випишіть стопки при кожному проході і стан списку після кожної збірки списку.

18. У кореневому сортуванні ключ можна також розглядати як послідовність бітів. Так, можна дивитися на цілочисельний 4-байтовий ключ як на послідовність з 32 бітів, а на 15-символьний ключ (що складається з 15

байтів) як на послідовність з 120 бітів. Потім ці послідовності бітів розбиваються на частини; розбивка задає число проходів і число стопок. Так,

наприклад, 120-бітовий ключ можна розбити на 12 частин по 10 бітів у кожній або на 10 частин по 12 бітів у кожній, або на 5 частин по 24 біта в кожній.

а) Припустимо, що ключ являє собою число в інтервалі від 0 до 264;

виберіть два можливих (поменше і побільше) значення числа бітів, які використовуються на кожному проході, і вкажіть відповідне число стопок і число проходів.

б) Припустимо, що ключ являє собою 40-байтову символьну рядок;

виберіть два можливих (поменше і побільше) значення числа бітів, які використовуються на кожному проході, і вкажіть відповідне число стопок і число проходів.

37

в) Чи можете ви на основі своїх відповідей на питання а) і б) дати загальні рекомендації про те, як вибирати розбиття ключа і число проходів?

19.Який буде порядок елементів списку [23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4] після застосування до нього етапу побудови піраміди при пірамідальному сортуванні?

20.Який буде порядок елементів списку [3, 9, 14, 12, 2 17, 15, 8, 6, 18, 20, 1] після застосування до нього етапу побудови піраміди при пірамідальному сортуванні?

21.Другий цикл for в пірамідальному сортуванні можна було б скоротити, додавши умову закінчення i> 3. Чи слід додати після цього цикл, і

якщо так, то що, для того, щоб остаточний список як і раніше був відсортованим? Чи приводять подібні зміни до зменшення числа порівнянь?

22.Доведіть, що список, заповнений елементами в порядку убування, дійсно являє собою піраміду.

23.Випишіть стан списку [7, 3, 9, 4, 2, 5, 6, 1, 8] після кожного проходу алгоритму злиття.

24.Випишіть стан списку [3, 5, 2, 9, 8, 1, 6, 4, 7] після кожного проходу алгоритму злиття.

25.Для алгоритму злиття найкращий випадок має місце, якщо всі елементи списку А менше за всіх елементів списку В. Однак це нічого не говорить про продуктивність всього алгоритму на довільному наборі вхідних даних. Скільки порівнянь зробить алгоритм злиття на списку [1, 2, 3, 4, 5, 6, 7, 8]? Взагалі, скільки порівнянь буде виконано на списку, елементи якого вже йдуть у зростаючому порядку?

26.Скільки в точності порівнянь зробить алгоритм злиття на списку

[8,7,6,5,4,3,2,1]?

27. Знайдіть порядок чисел від 1 до 8, при якому алгоритм злиття робить максимально можливе число порівнянь. Вказівка: Пройдіть процес сортування в зворотному напрямку.

38

28. Протрасуйте алгоритм швидкого сортування на списку [23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4]. Випишіть стан списку і стека значень (first, last, pivot)

перед кожним викликом. Підрахуйте число виконаних порівнянь і обмінів елементів місцями.

29.Протрасуйте алгоритм швидкого сортування на списку [3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1]. Випишіть стан списку і стека значень (first, last, pivot) перед кожним викликом. Підрахуйте число виконаних порівнянь і обмінів елементів місцями.

30.Скільки порівнянь виконає алгоритм швидкого сортування на списку, що складається з N однакових значень?

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

39

Практична робота № 6

Основні абстрактні типи даних

6.1 Теоретичні відомості

Абстракція даних (data abstraction) описує, що можна зробити з набором даних, ігноруючи питання «як це робиться?». Абстракція даних - це спосіб,

що дозволяє розробляти окремі структури даних незалежно від іншої частини програми. Інші модулі програми будуть знати, які операції можна виконувати над цими даними, але їм буде невідомо, яким чином зберігаються дані або як саме виконуються операції. Отже, як і колись, контракт відповідає на питання «що?», а не «як?». Отже, абстракція даних - це природне розширення функціональної абстракції. Абстрактний тип даних складається з даних і набору операцій над ними Набір даних у поєднанні з сукупністю операцій над ними називається абстрактним.

Розглянемо АТД список, який являє собою послідовність записів. У

нього є перший і останній елементи. За винятком цих елементів, у всіх інших є єдиний попередній елемент, або попередник (predessor), і єдиний наступний елемент, або наступник (successor). Перший елемент - голова (head), або початок (front) списку - не має попередника, а останній елемент - хвіст (tail),

або кінець (end) списку - не має наступника. Списки складаються з однотипних елементів. Що можна робити з елементами списку? Їх можна перераховувати, обчислюючи довжину списку, додавати в список, видаляти з нього, переглядати (витягати (retreave)). Елементи списку разом з операціями над ними утворюють абстрактний тип.

Операції над абстрактним списком

1.Створити порожній список.

2.Видалити список.

3.Визначити, чи порожній список.

4.Визначити кількість елементів у списку.

5.Вставити елемент у вказану позицію списку.

6.Видалити елемент, що знаходиться у зазначеній позиції списку.

40