18

Лабораторна робота № 4

"Розробка та дослідження ефективності методів сортування"

1. МЕТА РОБОТИ

Вивчення, реалізація та дослідження ефективності методів сортування даних.

2. ТЕОРЕТИЧНІ ВІДОМОСТІ

2.1. Задача сортування

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

Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все часова ефективність та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування вставкою) не є дуже ефективними.

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

Алгоритм сортування вибором ефективніше сортування обміном за критерієм М(n), тобто за кількістю перестановок, але також є не дуже ефективним. З цих причин було розроблено деякі нові алгоритми сортування, що отримали назву швидких алгоритмів сортування. Це такі алгоритми, як сортування деревом, пірамідальне сортування, швидке сортування Хоара та метод цифрового сортування.

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

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

Однак справедливе й зворотне. Яким би гарним і ефективним не був обраний алгоритм, але якщо в якості підзадачі він використовує "поганє" сортування, то вся робота з його оптимізації виявляється марною. Невдало реалізоване сортування вхідних даних здатне помітно знизити ефективність алгоритму в цілому.

2.2. Класифікація методів сортування

Методи сортування розділяються на внутрішні (які обробляють масиви) і зовнішні (що працюють тільки з файлами). Ми будемо розглядати тільки внутрішні методи сортування. Важлива особливість методів полягає в тому, що алгоритми не вимагають додаткової пам'яті: вся робота з впорядкування виконується всередині того самого масиву.

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

Внутрішнє сортування

Зовнішнє сортування

Прості методи

Покращені методи

Просте злиття

Природнє злиття

Збалансо-ване злиття

Багато-фазне сор-тування

Метод простої вставки

Метод простого вибору

Метод простого обміну

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

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

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

Шейкер- сортування

Метод бінарного включення

рис.1. Класифікація методів сортування

3. Порядок виконання роботи

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

2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.

3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.

4. Протестувати програму згідно зі складеною системою тестів і, при потребі, відкоректувати текст програми. Проаналізувати отримані результати.

5. Написати контрольне опитування по темі.

6. Оформити звіт по роботі.

Без підготовкі до лабораторної роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.

4. Завдання на лабораторну роботу

4.1. Завдання 1

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

Провести дослідження побудованого методу за такою схемою:

1). Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).

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

3). Дослідити метод cортування на стійкість.

4). Дослідити метод cортування на економність використання пам’яті.

5). Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).

6). Дослідити ефективність методу. Для цього визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому ( ) і в найгіршому ( ) випадках. Середні значення кількості порівнянь ( ) і кількості перестановок ( ) визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей.

7). Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості. Зробити висновки про ефективність методу.