Дослідження ефективності алгоритмів сортувань для різних структур та розмірностей даних
Алгоритм концептуально простий, вимагає вкладених циклів. Час роботи. На практиці алгоритм може працювати так само швидко, як сортування вставками.
Алгоритм знаходить перше місце, де два сусідні елементи стоять у неправильному порядку та змінює їх місцями. Він користується тим фактом, що обмін може породити нову пару, яка стоїть у неправильному порядку, лише до або після переставлених елементів. Він допускає, що елементи після поточної позиції відсортовані, отже, потрібно лише перевірити позицію до переставлених елементів.
Сортування вставками – досить простий алгоритм. Масив ділиться на 2 частини: відсортовану та невідсортовану. На кожному кроці береться черговий елемент з невідсортованої частини та входить у відсортовану. Має високу обчислювальну складність O(n?). Відсортовано початок масиву A1, A2, …, Ai-1. Залишок масиву Ai, An не відсортований. На черговому кроці Ai входить у відсортовану частину на відповідне місце. Приклад такого сортування – сортування за допомогою двійкового дерева.
Сортування злиттям — алгоритм сортування, який упорядковує списки (або інші структури даних, доступ до елементів яких можна отримувати лише послідовно, наприклад потоки) у певному порядку. Це сортування – гарний приклад використання принципу «розділяй і володарюй». Спочатку завдання розбивається на кілька підзадач меншого розміру. Потім ці завдання вирішуються за допомогою рекурсивного виклику або безпосередньо, якщо їхній розмір досить малий. Нарешті, їх рішення комбінуються, і виходить вирішення вихідного завдання.
Блокове сортування (Кишенькове сортування, кошикове сортування, англ. Bucket sort) - Алгоритм сортування, в якому сортовані елементи розподіляються між кінцевим числом окремих блоків(кишень, кошиків) так, щоб усі елементи в кожному наступному по порядку блоці були завжди більшими (або меншими), ніж у попередньому. Кожен блок потім сортується окремо або рекурсивно тим же методом, або іншим. Потім елементи поміщаються назад в масив. Цей тип сортування може мати лінійний час виконання.
Переваги: відноситься до класу швидких алгоритмів з лінійним часом виконання O(N) (на вдалих вхідних даних).
Недоліки: сильно деградує при великій кількості мало відмінних елементів або на невдалій функції отримання номера кошика за вмістом елемента. У деяких таких випадках для рядків, що виникають у реалізаціях заснованого на сортуванні рядків алгоритму стиснення BWT, виявляється, щоб швидке сортування рядків у версії Седжвіка значно перевищує блокове сортування швидкістю.
Цей метод у тому, що порівнюються елементи, які стоять як поруч, а й з відривом друг від друга. Інакше кажучи - сортування вставками чи сортування простими обмінами з попередніми «грубими» проходами.
При даному сортуванні спочатку порівнюються та сортуються між собою ключі, що віддаляються один від одного на деякій відстані d. Після цього процедура повторюється для менших значень d, а завершується сортування Шелла упорядкуванням елементів при d = 1
Використаний мною власний метод визначення ключів полягає у використанні емпіричної послідовності чисел, яка оптимально підійшла б для впорядкування масивів різної довжини.
Швидке сортування використовує стратегію «розділяй і володарюй». Кроки алгоритму такі:
Вибираємо в масиві певний елемент, який називатимемо опорним елементом. З погляду коректності алгоритму вибір опорного елементабайдужий. З точки зору підвищення ефективності алгоритму вибиратися повинна медіана, але без додаткових відомостей про дані, що сортуються, її зазвичай неможливо отримати. Відомі стратегії: вибирати постійно той самий елемент, наприклад, середній чи останній за становищем; вибирати елемент із випадково вибраним індексом.
Операція поділу масиву: реорганізуємо масив таким чином, щоб усі елементи, менші або рівні опорному елементу, виявилися ліворуч від нього, а всі елементи, більші за опорний — праворуч від нього. Звичайний алгоритм операції:
Два індекси - l і r, прирівнюються до мінімального і максимального індексу масиву, що розділяється відповідно.
Обчислюється індекс опорного елемента m.
Індекс l послідовно збільшується до m до тих пір, поки l елемент не перевищить опорний.
Індекс r послідовно зменшується до m до того часу, поки r-й елемент виявиться менше чи дорівнює опорному.
Якщо r = l – знайдена середина масиву – операція поділу закінчена, обидва індекси вказують на опорний елемент.