Сортування є однією з фундаментальних алгоритмічних задач програмування. Рішенням проблем, пов'язаних з упорядкуванням елементів деякого безлічі присвячена велика кількість досліджень і визначено спектр алгоритмів.
Сортування слід розуміти як процес перегрупування заданої множини об'єктів в певному порядку з метою полегшити подальший пошук заданого елемента в даній множині, причому під сортованими елементами можуть розумітися довільні об'єкти від чисел і символів до математичних формул. У будь-якому випадку, сортування можна представити таким чином:
- Дан ряд елементів (A1, A2, ..., An). Необхідно здійснити їх перестановку в порядку (Ak1, Ak2, ... Akn) так, щоб елементи підпорядковувалися функції впорядкування F (Ak1) <= F(Ak2) <= … <= F(Akn), при этом вводят понятие "ключ сортировки".
- Ключем сортування називають атрибут елемента, за значенням якого здійснюється впорядкування.
Будь алгоритм сортування складається з 3 частин:
1) порівняння. визначальне впорядкованість пари елементів;
2) перестановка. що дозволяє міняти місцями пару елементів (A2 на місце A1, A1 на місце A2);
3) власне сортують алгоритм. здійснює порівняння і перестановку елементів до тих пір, поки всі елементи множини не будуть упорядковані.
Існує досить широкий спектр алгоритмів сортування, кожен з яких має певні характеристики і зручний для застосування в тому чи іншому випадку. Для оцінки та порівняння алгоритмів сортування введений набір параметрів:
1) час сортування - основний параметр, що характеризує швидкодію алгоритму.
2) пам'ять - параметр, який характеризується тим, що для роботи алгоритму потрібна додаткова пам'ять для тимчасового зберігання сортируемих значень. При оцінці використовуваної пам'яті не враховується обсяг пам'яті, який використовується для зберігання вихідного масиву (безлічі).
3) стійкість - параметр, який відповідає за те, що сортування не змінює взаємного розташування рівних за значенням елементів. Стійкість правильна, якщо елементи впорядковані по вторинним ключам, тобто по атрибутам, не відображених в основному ключі сортування.
1a 3q 1b 1c 2z: вихідний масив (індекс, значення)
1a 1b 1c 2z 3q: стійка сортування
1c 1b 1a 2z 3q: нестійка сортування
4) природність поведінки - параметр, який вказує на ефективність сортування при обробці вже відсортованих або частково впорядкованих даних. Вважається, що алгоритм поводиться природно, якщо він враховує цю характеристику вхідної послідовності (краще або не гірше).
Всі виконувані алгоритми сортування можуть бути розділені на 2 основні класи:
1) внутрішня сортування. алгоритми внутрішнього сортування визначають процес упорядкування елементів, які розташовуються в оперативній пам'яті обчислювального пристрою. При цьому передбачається, що в довільний момент часу можна отримати доступ до будь-якого елементу сортується безлічі. Внутрішня сортування застосовується у всіх випадках, крім однопрохідного читання і запису сортируемих даних.
2) зовнішня сортування. сортування при проведенні упорядкування даних використовує зовнішні носії. Зовнішня сортування дозволяє обробляти великі обсяги даних, які не поміщаються в оперативну пам'ять. Це накладає обмеження, пов'язане з тим, що доступ до сортируемое елементам здійснюється тільки послідовно, тобто в один довільний момент часу можна звернутися тільки до 1 поточному сортируемое елементу.
Методи внутрішнього сортування діляться на універсальні і спеціальні. Універсальні -> прості і поліпшені. Прості і поліпшені методи відрізняються своєю ефективністю. Спеціальні методи призначені для сортування інформації певної структури.
Прості методи сортування масивів.
До простих методів сортування масивів відносяться:
Сортування бульбашкою - найбільш простий для реалізації і розуміння алгоритм сортування, але ефективний він лише для невеликих масивів. Складність алгоритму - n ^ 2.
Даний алгоритм вважається навчальним і практично не застосовується поза навчальної літератури; замість нього на практиці застосовуються більш ефективні алгоритми сортування. У той же час цей алгоритм лежить в основі деяких більш досконалих алгоритмів, таких як пірамідальна сортування і швидке сортування.
Алгоритм складається з повторюваних проходів по сортованого масиву. За кожен прохід елементи послідовно порівнюються попарно і, якщо порядок в парі невірний, виконується обмін елементів. Проходи по масиву повторюються N-1 раз або до тих пір, поки на черговому проході не опиниться, що обміни більше не потрібні, що означає - масив відсортований. При кожному проході алгоритму по внутрішньому циклу, черговий найбільший елемент масиву ставиться на своє місце в кінці масиву поруч з попереднім «найбільшим елементом», а найменший елемент переміщається на одну позицію до початку масиву ( «спливає» до потрібної позиції як бульбашка у воді, звідси і назва алгоритму).
Сортування бульбашкою не змінює взаємного розташування рівних елементів і не використовує додаткової пам'яті.
- Алгоритм є природним і стійким.
- Висока обчислювальна складність алгоритму.
Сортування вибором - один з класичних методів упорядкування послідовності, що грунтується на операції порівняння.
Може бути як стійким, так і нестійким.
- Знаходиться мінімальний (максимальний) елемент послідовності. Для цього перший елемент порівнюється з другим, перший з третім і т.д. Номер знайденого елемента позначається.
- Якщо індекс першого елемента не тотожний цьому елементу, то вони обмінюються значеннями.
- Сортування триває на відсортованої частини масиву.
Число порівнянь: N ^ 2
- Цьому методу сортування віддається перевага в тих випадках, коли записи файлу величезні, а ключі займають незначне місце.
- Даний алгоритм виробляє найбільш меншу кількість переміщень даних, ніж метод вибору.
- Процес знаходження мінімального елемента за один прохід не дає відомостей про те, де буде знаходитися наступний мінімальний елемент.
- На великих обсягах даних дана сортування є неефективною.
Даний алгоритм вибудовує результуючий масив по одному елементу за раз. Він набагато менш ефективний на великих списках, ніж поліпшені методи сортування (qsort / hsort). Однак, у даного алгоритму є такі переваги:
- Ефективний на невеликих наборах даних
- Найкращий випадок - O (n)
- Вимагає тільки O (1) додаткової пам'яті
Недоліки - висока обчислювальна складність O (n ^ 2).
На кожному кроці вибирається один з елементів вхідних даних і вставляється на потрібну позицію в уже відсортованому списку до тих пір, поки набір вхідних даних не буде вичерпаний. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай елементи вставляються по порядку їх появи у вхідному масиві.
Сортування злиттям - алгоритм сортування, який впорядковує списки (або інші структури даних, доступ до яких можна отримувати тільки послідовно) в певному порядку. Спочатку завдання розбивається на підзадачі меншого розміру, потім вони вирішуються за допомогою рекурсивного виклику або безпосередньо, якщо їх розмір досить малий. Після цього їх вирішення комбінуються, і виходить рішення вихідної задачі. Використовується для зовнішньої сортування.
Найгірший випадок - O (n log (n)).
Сортований масив розбивається на 2 масиву приблизно однакового розміру. Кожна з вийшов частин ділиться тим же самим алгоритмом до того, поки довжина кожної частини нічого очікувати дорівнює 1; потім ці частини масиву з'єднуються в один і упорядковано.
- Сортування є стійкою.
- Ефективна при обробці даних з великим часом доступу.
- Найкращий спосіб сортування пов'язаних списків.
- Алгоритм зручний для структур з послідовним доступом до елементів.
- Вимагає додатковий простір (O (1)).
- Поступається за швидкодією швидкої сортування.