Нарешті ми підійшли до розбору алгортмів сортування – почнемо з найпростіших і будемо поступово підвищувати складність. Сьогодні ми розглянемо прості алгоритми сортування. Ці алгоритми дійсно є доволі простими, як для розуміння, так і в реалізації. Однак, незважаючи на назву, використання таких алгоритмів простим назвати не вийде. На жаль, у цього типу алгоритму є ряд недоліків, а саме – низка ефективність і висока обчислювальна складність.
Сортування включенням
При цьому сортуванні вхідний масив послідовно перебирається від початку до кінця. Кожний наступний обраний елемент переміщується в масиві назад таким чином, щоб він опинився між двома елементами, попередній з яких буде менше обраного числа, а наступний — більше. Відповідно, якщо при виборі елемента він відразу більший за попередній, то переміщувати його не потрібно.
Один з варіантів реалізації цього алгоритму виглядатиме ось так:
А тепер щодо складності цього алгоритму.
Складність за часом:
Найгірший час: O(n2) для порівнянь та перестановок;
Середній час: Θ(n2) для порівнянь та перестановок;
Кращий час: Ω(n) для порівнянь і Ω(1) для перестановок.
Складність за необхідною пам’яттю: O(n) плюс 1 комірка пам’яті для буферизації обраного елемента.
Сортування вибором
Алгоритм сотрування вибором виглядає наступним чином. Спочатку відбувається повний прохід масивом у пошуках найменшого елементу. Далі знайдений мінімальний елемент міняється місцями з елементом, який стоїть на нульовій позиції. А далі ці дії повторюються для масиву, що залишився, тобто відшукується мінімальний елемент у підмасиві, що залишився і розміщується на 1 позиції і так далі, доки масив не буде повністю відсортовано.
Один з варіантів реалізації виглядає ось так:
Обчислювальна складність цього алгоритму, як і попереднього, не вражає.
Складність за часом:
Найгірший час: O(n2);
Середній час: Θ(n2);
Кращий час: Ω(n2).
Складність за необхідною пам’яттю: O(n) плюс 1 комірка пам’яті для буферизації обраного елементу.
Цей алгоритм має досить логічну модифікацію, яка має назву «двустороннє сортування вибором». Адже якщо ми все одно проходимо масивом, чому б не шукати відразу мінімальний та максимальний елемент і вставляти ці елементи в кінець та на початок масиву?
Здається, таким чином ми прискоримось у 2 рази — але ні. Кількість перестановок і порівнянь залишиться такою ж як і була, а отже й обчислювальна складність алгоритму суттєво не зміниться.
На цьому ми поки що зупинимося. Звичайно, до простих сотрувань можна віднести й улюблене всіма сортування бульбашкою. В наступній статті ми як раз і поговоримо про бульбашкове сортування та його модифікації.
_03132332.png)
