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

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

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

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

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

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

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

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

 

 

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

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

 

 

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

 

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