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

206

Продовження таблиці 19

207

Закінчєння таблиці 19

Проаналізуємо отримані результати тестування алгоритмів сортування за складністю їх виконання.

Серед усіх прямих методів можна визначити, що найгірше себе поводить метод обміну. Причому за результатами тесту­вання цього методу дуже добре видно, якою є «вартість» опера-цій порівняння та обміну елементів масиву. Наприклад, для N - 30 000 час виконання алгоритму на впорядкованому за зростанням масиві становить 9,615 с, на випадковому — 18,79 с, на впорядкованому за спаданиям - 23,35 с. Це означав, що, впорядковуючи за зростанням уже впорядкований масив, алго­ритм прямого обміну виконує лише операції порівняння всіх пар елементів і не виконує операцій обміну. Упорядковуючи за зростанням масив елементів, значения яких є випадковими числами, виконуються ті самі операції порівняння та близько половини елементів обмінюються своїми значениями. Під час упорядкування за зростанням масиву елементів, які були впо-рядковані за спаданням, відбуваються ті самі операції порів-няння та всі елементи міняються місцями. Це означав, що час виконання обміну значень елементів масиву вдвічі більший, ніж їх порівняння. Тому можна зробити висновок, що при складанні алгоритмів бажано уникати не тільки зайвих порів-нянь, а й у першу чергу зайвих обмінів!

Тестування методу включения доводить той факт, що він дуже чутливий до часткової впорядкованості вхідного масиву. Час упорядкування впорядкованого масиву не фіксується зов-сім, незалежно від кількості елементів масиву. А для впо­рядкованого за спаданням масиву (N - 30 000) час виконання алгоритму вдвічі більший (13,35 с), ніж для випадково за-даних значень елементів (6,648 с). Це пояснюється тим, що в упорядкованому за спаданням масиві жоден елемент не стоїть на своему місці щодо впорядкування за зростанням і для всіх цих елементів треба робити обміни місцями, а у випадковому масиві таких елементів є близько половини.

Метод выбору абсолютно нечутливий до часткової впоряд-кованості вхідного масиву. Він за однаковий час сортуе як повністю впорядкований масив, так і випадково сформований масив. Але в деяких випадках він досить непогано виглядае на фоні інших методів сортування.

•ZQS

Для покращених методів порівняльна картина така. Метод бінарного включения підтверджує свою ефективність порів-няно з методом шейкерного сортування. Слід зазначити, що обидва ці методи абсолютно не реагують на кількість елементів масиву у випадку, коли він уже впорядкований за зростанням: алгоритми обмежуються лише операціями порівняння і не ви-конують жодних обмінів. Час виконання на будь-яких масивах не фіксується. На двох інших масивах — випадковому та впо-рядкованому за спаданиям — відношення часу виконання ал-горитмів різне. Для методу бінарного включения час для цих двох варіантів масивів відноситься приблизно як 1:2, а для шейкерного сортування як 1:1,5. Це можна пояснити так: метод бінарного включения робить швидкий пошук місця положения елемента a_t у масиві a_v ..., о,., але з постійним рекурсивним поділом цього масиву навпіл, а метод шейкерного сортування на кожному кроці враховує те, що певні частини масиву на початку й у кінці вже впорядковані. Але загалом переваги методу бінарного включения перед методом шей­керного сортування незаперечні.

У свою чергу метод бінарного включения значно покращуе результати сортування на тих самих масивах порівняно з ме­тодом прямого включения, а метод шейкерного сортування -порівняно з методом обміну.

Тепер перейдемо до удосконалених методів. Лідером у цій групі, так само як і серед усіх методів загалом, є метод швидко-го сортування. 3 таблиці 19 видно, що для різних як за дов-жиною, так і за розташуванням елементів масивів не вдалося зафіксувати час виконання цього алгоритму. Друге місце за ним посідає метод пірамідального сортування: лише на масиві у 30 000 елементів фіксується зовсім незначний час виконання цього алгоритму, причому абсолютно однаковий для всіх трьох видів масивів - 0,055 с. Метод Шелла, який використовує принцип бар'єрів, посідає трете місце, оскільки з-за викорис-тання додаткової пам'яті виникають проблеми з обмеженням на розмірність масиву вхідних даних. Алгоритм, що реалізує метод Шелла без використання бар'єрів, виявився неефек-тивним за часом виконання. Наприклад, для N = 10 000 і для довільного розташування елементів масиву він дає 8,132 с.

Особливе місце, як і передбачалося, займають методи сор­тування послідовностей. Метод прямого злиття не дає мож-ливості зафіксувати час виконання алгоритму для масивів, значения елементів яких займае 2 байти (word або integer) i кількість яких не перевищує 15 000. Для N = 20 000 та N - 30 000 можна розмістити в пам'яті комп'ютера лише зна­чения елементів типу byte, i час виконання алгоритму є дуже незначним, але все ж таки фіксується: 0,055 с. Використання

209

методу природного злиття є більш обмеженим із-за викорис-тання додаткових масивів. Уже для N = 5000 його можна вико-ристовувати лише для значень елементів масиву типу byte. А при ЛГ = 15 000 і більше неможливо розмістити в пам'яті комп'ютера навіть і такі елементи.

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

Остання група методів - методи лінійного сортування. На основі даних таблиці 19 можна констатувати факт, що сорту­вання підрахунком є дуже ефективним методом і не посту-пається наикращим наведеним вище методам. Є лише один недолік: обмеження на проміжок зміни значень елементів масиву, що сортуються. Ці обмеження повинні бути такими, щоб була можливість розмістити в пам'яті комп'ютера масив, де буде фіксуватися кількість різних елементів вхідного ма­сиву. Розміщенням у пам'яті вхідного масиву можна знехту-вати. Тестування проводилося для значень елементів типу word. Метод цифрового сортування є не менш ефективним і підтверджує цей статус за результатами тестування. Однак негативним моментом є обмеженість використання цього мето­ду з-за того, що він вимагає створення декількох додаткових масивів. Тому в таблиці, вже починаючи з N - 10 000, тестуван­ня цього методу стало неможливим.

На завершения аналізу всіх методів сортування можна зробити такі висновки:

• наикращим методом при будь-яких значениях елементів масиву та їх кількості є метод швидкого сортування;

• для кожного конкретного випадку значень елементів вхід-ного масиву можна застосувати й інші аналогічні за ефектив-ністю швидкому сортуванню методи: для майже впорядкова-них масивів; для масивів, значения елементів яких належать заданому проміжку, тощо;

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

Запитання для самоконтролю

1. Як на апаратному рівні можна визначати час виконання программ?

2. Яким є порівняльний аналіз методів прямого сортування?

3. Яким є порівняльний аналіз покращених методів сортування?

4. Яким є порівняльний аналіз удосконалених методів сортування?

1. Яким є порівняльний аналіз методів сортування послідовнос-тей?

210

6. Яким є порівняльний аналіз методів лінійного сортування?

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

Завдання

1. Розробити програму, яка створює масив із п елементів, упорядкованих за зростанням.

2. Розробити програму, яка створює масив із п елементів, значения яких є випадковими.

3. Розробити програму, яка створює масив із п елементів, упорядкованих за спаданиям.

4. За допомогою програм, розроблених у пунктах 1-3, ство-рити відповідні масиви для 1000 < п < 10 000 та зберегти їх у файлах.

5. Протестувати алгоритми, що реалізують прямі методи сортування, на вхідних масивах, створених у пункті 4, фік-суючи час їх виконання. Порівняти отримані результати тесту-вання.

6. Протестувати алгоритми, що реалізують покращені ме­тоди сортування, на вхідних масивах, створених у пункті 4, фіксуючи час їх виконання. Порівняти отримані результати тесту вання.

7. Протестувати алгоритми, що реалізують удосконалені ме­тоди сортування, на вхідних масивах, створених у пункті 4, фіксуючи час їх виконання. Порівняти отримані результати тестування.

8. Протестувати алгоритми, що реалізують методи сортування послідовностей, на вхідних масивах, створених у пункті 4, фік-суючи час їх виконання. Порівняти отримані результати тес­тування.

9. Протестувати алгоритми, що реалізують методи лінійного сортування, на вхідних масивах, створених у пункті 4, фік-суючи час їх виконання. Порівняти отримані результати тес­тування.

10. Зробити письмовий аналіз завдань 5-9.

211

Література

1. Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы.: Пер. с англ.: Уч. нос. -М.: Издательский дом «Вильяме», 2000. — 384 с.

2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - 2-е изд., испр. - СПб.: Невский Диалект, 2001. - 352 с: ил.

3. Зубов B.C. Справочник программиста. Базовые методы ре­шения графовых задач и сортировки. - М.: Информацион­но-издательский Дом «Филинъ», 1999. - 256 с.

4. Касаткин В.Н., Верлань А.Ф. Основы информатики и вы­числительной техники. - К.: Рад. шк., 1989. - 237 с.

5. Касаткин В.Н. Необычные задачи математики. - К.: Рад. шк., 1987. - 128 с.

6. Кнут Дональд Э. Искусство программирования: Т. 3. Сор­тировка и поиск., 2-е изд.: Пер. с англ. - М.: Издательский дом «Вильяме», 2004. - 832 с.

7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2001. - 960 с.

8. Макконел Дж. Анализ алгоритмов. Вводный курс. - М.: Техносфера, 2002. - 304 с.

9. Окулов СМ. Основы программирования. - М.: ЮНИМЕ-ДИАСТАЙЛ, 2002. - 424 с.

10. Фомин СЛ. Системы счисления. - 5-е изд. - М.: Наука. Гл. ред. физ.-мат. лит., 1987. - 48 с. - (Попул. лекции по мат.)

212

ЗМІСТ

Від автора 3

Розділ I. МЕТОДИКА РОЗРОБКИ ЛЛГОРИТМІВ,

ОЦШКАЇХ ЕФЕКТИВНОСП 5

Створеішя алгоритму 5

Математична модель, вибір структури даних 6

Пошук оптимального алгоритму розв'язування 7

Узагальнення та аналіз екстремальних ситуацій 10

Оцінка та аналіз ефективності алгоритму 13

Запитання для самоконтролю 19

Налагодження алгоритму 20

Планування, покрокова деталізація

та представления алгоритму 20

Допоміжні задачі 21

Реалізація алгоритму мовою програмування 23

Запитання для самоконтролю 25

Розділ II. СИСТЕМИ ЧИСЛЕНИЯ. ПРЕДСТАВЛЕНИЯ

ШФОРМАЦІЇ У КОМП'ЮТЕРІ 26

Поняття систем числевня 26

Арифметичні дїї в позиційних системах числения 29

Переведения чисел з однієї системи числення в inшу 36

Переведения чисел з 10-Ї системи числення

у систему числення 3 основою Р 36

Переведения чисел із системи числення з основою Р

у 10-ву систему числення 39

■ Зв'язок між системами числення з основою 2* 40

Одяорозрядний суматор 43

Запитання для самоконтролю 47

Завдання 47

Чнслова інформація 52

Цілі числа 52

Дійсні числа 55

Текстова інформація 56

Символи 56

Рядки 57

Запитання для самоконтролю 57

Розділ III. СТРУКТУРИ ДАНИХ 58

Проста змінна 59

Запитання для самоконтролю 59

Масив 60

Запитання для самоконтролю 61

Стек 62

213

Запитання для самоконтролю 65

Заедания 65

Черга 65

Запитання для самоконтролю 70

Заедания 70

Дек 70

Запитання для самоконтролю 72

Заедания 73

Зв'язний список 73

Запитання для самоконтролю 82

Заедания 83

Дерево. Бінарне дерево 83

Запитання для самоконтролю 94

Заедания 95

Хеит-таблиця 96

Запитання для самоконтролю 104

Заедания 105

Розділ IV. ПОШУКОВІ АЛГОРИТМЕ 106

Осяовні поняття пошукових алгоритмів 106

Лінійний пошук 107

Алгоритм лінійного пошуку 107