%D0%9E%D0%BF%D0%B8%D1%81 %D0%BF%D1%80%D0%B5%D0%B4%D0%BC%D0%B5%D1%82%D0%BD%D0%BE%D1%97 %D0%BE%D0%B1%D0%BB%D0%B0%D1%81%D1%82%D1%96 - ESEI-ZNU/SortingAlgorithms GitHub Wiki

Огляд предметної області: Реалізація аналізу алгоритмів сортування

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

Ключові функції:

Клас масиву цілих чисел(Array): Методи для створення, керування та отримання даних з масиву цілих чисел. Реалізація операцій вставки, видалення та зміни елементів.

Засоби доступу (Accessors): Методи для доступу до елементів масиву. Забезпечення безпечного та ефективного доступу до даних.

Клас ітератора(Iterator): Реалізація ітератора для послідовного проходження через елементи масиву цілих чисел. Підтримка ітерації в обидва напрямки: від початку до кінця та від кінця до початку.

Заключення: Розроблена програма забезпечує можливість об'єктивно порівняти різні алгоритми сортування з точки зору їх ефективності та продуктивності. Це дозволяє розробникам та інженерам вибирати найбільш підходящий алгоритм для конкретних завдань та оптимізувати роботу з даними.

Посилання https://moodle.znu.edu.ua/course/view.php?id=8599

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

У кожній ітерації проходимо через весь список, порівнюючи кожну пару сусідніх елементів.

Якщо пара елементів не відсортована у правильному порядку, ми їх обмінюємо.

Після кожної ітерації найбільший (або найменший, залежно від порядку сортування) елемент викидається на правильне місце в кінці списку.

Процес повторюється до тих пір, поки весь список не буде відсортований.

Опис методу

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

Порівняння та обмін: Як і в сортуванні бульбашкою, в кожному проході пари сусідніх елементів порівнюються між собою, і якщо вони не відсортовані у правильному порядку, вони обмінюються місцями.

Рух в обидва напрямки: Після того, як один прохід від початку до кінця завершується, алгоритм повертається назад, пройшовши від кінця до початку. Цей процес продовжується до тих пір, поки всі елементи не будуть відсортовані.

Ефективність: Шейкерна сортування може бути більш ефективною, ніж звичайне сортування бульбашкою, оскільки вона дозволяє обмінювати елементи в обох напрямках. Це дозволяє витягнути найбільші та найменші елементи швидше на свої місця.

Опис методу

Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність $n^2$, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.

Алгоритм працює таким чином:

1. Знаходить у списку найменше значення
2. Міняє його місцями із першим значенням у списку
3. Повторює два попередніх кроки, доки список не завершиться (починаючи з наступної позиції)

Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.

Ось приклад сортування масиву з п'яти елементів за даним алгоритмом:

64 25 12 22 11
11 25 12 22 64

11 12 25 22 64
11 12 22 25 64

Сортування вставками також може працювати зі списками, які підтримують операції додавання і видалення, як то зв'язаний список. У такому разі, більш зручно видаляти зі списку найменший елемент, і вставляти його в кінець відсортованої частини масиву. Наприклад:

64 25 12 22 11
11 64 25 12 22
11 12 64 25 22
11 12 22 64 25
11 12 22 25 64

Аналіз

Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найменшого елементу вимагає перегляду усіх n елементів (у цьому випадку n − 1 порівняння), і після цього, перестановки його до першої позиції. Знаходження наступного найменшого елементу вимагає перегляду n − 1 елементів, і так далі, для $(n − 1) + (n − 2) + … + 2 + 1 = n(n − 1) / 2 ∈ Θ(n^2)$ порівнянь (дивіться арифметична прогресія). Кожне сканування вимагає перестановки однієї пари елементів, тож всього потрібно (n − 1) перестановок (останній елемент знаходитиметься на своєму місці).

Опис алгоритму

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

Переваги сортування вставками

• Простий для реалізації та зрозуміння.
• Добре працює для малих наборів даних або вже відсортованих наборів.

Недоліки сортування вставками

• Ефективність залежить від розміру вхідних даних.
• Може бути повільним для великих наборів даних.

Графічний приклад роботи: