sort_mass_ukr

Інформатика - 9

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

Алгоритми сортування даних

Алгоритм сортування

алгоритм для упорядкування элементів списку за одним з полів, яке є критерієм порядку та зветься ключом сортування.

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

Сортування вибором (Selection sort)

• може бути стійким та нестійким (однакові з точки зору параметра сортування елементи можуть змінювати своє розміщення)
• не є ефективним при сортуванні великих масивів

1. Порівнюються перші два елементи списку.
2. Якщо перший елемент більший (для сортування за зростанням), вони переставляються місцями, інакше залишаються як є.
3. З наступною парою елементів процес повторюється.
4. Дії тривають до останньої пари елементів списку.
5. По досягненні кінця списку процес повторюється, поки список не буде відсортовано.

Сортування простим обміном / бульбашкове сортування (Bubble sort)

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

щоб «усунути» елементи з невеликими значеннями в кінці масиву, які уповільнюють роботу алгоритму, при «розчісуванні» спочатку береться досить велика відстань між значеннями, що порівнюються, а потім вона звужується аж до мінімального

шейкерне сортування (сортування змішуванням)

при тому ж попарному порівнянні сусідніх елементів відрізняється від бульбашкової двоспрямованістю: сортування відбувається в обох напрямках, змінюючи напрямок при кожному проході

сортування гребінцем

Удосконалення сортування бульбашкою

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

Сортування включенням / сортування вставлянням (Insertion sort)

• є "стійким " (однакові з точки зору параметра сортування елементи не змінюють своє розташування)
• не відноситься до ефективних алгоритмів
• більш ефективний на невеликих масивах або масивах, частково відсортованих

1. спочатку порівнюються і сортуються між собою значення, що стоять один від одного на деякій відстані d
2. після процедура повторюється для деяких менших значень d
3. сортування завершується упорядкуванням елементів при d = 1

Сортування Шелла (Shell sort)

• удосконалений варіант сортування включенням з попередніми «грубими» проходами
• ефективність методу Дональда Шелла в певних випадках забезпечується тим, що елементи «швидше» стають на свої місця
• алгоритм не є стійким (стабільним)

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

Сортування злиттям (Merge sort)

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

1. з масиву вибирається один елемент, зазвичай званий опорним
2. інші елементи в масиві перерозподіляються так, щоб елементи, менші за опорний, опинилися до нього, а більші або рівні - після
3. рекурсивно застосовуються кроки 1-2 до підмасивів праворуч і ліворуч від опорного значення.

Швидке сортування, сортування Гоара (Quicksort)

• часто називається qsort за іменем у стандартній бібліотеці мови С
• розроблене англійським інформатиком Чарльзом Гоаром в 1960 році
• один з найшвидших відомих універсальних алгоритмів сортування масивів, не є стійким

"куча"

1. елементи масиву шикуються у вигляді бінарного сортувального дерева (купи, heap), де найбільший елемент є вершиною дерева
2. цей елемент вилучається з купи і розміщується в кінці списку
3. купа перебудовується і новий найбільший елемент розміщується перед останнім елементом у спискукроки 2-3 повторюються до впорядкування масиву

Пірамідальне сортування, сортування купою (Heap-sort)

• запропонований Дж. Вільямсом у 1964 році
• може розглядатися як удосконалене сортування бульбашкою, в якій елемент спливає (min-heap) або тоне (max-heap) багатьма шляхами
• дає виграш на великих масивах

Розмір масиву (кількість чисел)

Час сортування, секунд

Час сортування масивів цілочисельних значень, що не перевищують розміри масиву

Оцінювання алгоритмів сортування

• швидкість виконання (обчислювальна складність)
• ефективність використання пам'яті (потреба додаткової пам'яті)
• стабільність / стійкість (незмінюваність взаємного розташування елементів з однаковими ключами)

Джерела інформації та корисні посилання

1. Алгоритм сортування (Вікіпедія, стаття)https://uk.wikipedia.org/wiki/Алгоритм_сортування
2. Sorting strategies (плейлист YouTube): алгоритми сортування в народних танцяхhttps://www.youtube.com/watch?v=Xw2D9aJRBY4&list=PLcX11VWS1PdA4dSPip8-1JfKxFa32X53y
3. Стабільне сортування (Вікіпедія, стаття)https://uk.wikipedia.org/wiki/Стабільне_сортування
4. П’ять алгоритмів сортування на Python, які вам треба знати ("Телетайп")https://teletype.in/@cursor.education/6aIKSINQ7
5. Сортування (Чернігівська обласна інтернет-школа "Юний програміст")http://choippo.cn.sch.in.ua/navchaljni_temi/sortuvannya/
6. Сортировки в гифках: 8 самых популярных алгоритмов (Proglib.Academy)https://proglib.io/p/sort-gif/
7. Sorting Algorithms Animations (Toptal)https://www.toptal.com/developers/sorting-algorithms