Лабораторная работа «сортировка»

Лабораторна робота №5
Прості методи сортування
Мета роботи
: реалізація простих алгоритмів сортування та дослідження їх
характеристик (швидкодія, необхідний обсяг пам'яті, застосування тощо).
Методичні вказівки
Під
сортуванням
звичайно розуміють процес перестановки об'єктів заданої
множини у певному порядку.
Мета сортування
– полегшення подальшого пошуку елементів у відсортованій
множині. У цьому сенсі елементи сортування присутні майже у всіх завданнях.
1. Сортування бульбашкою
Розташуємо масив зверху вниз, від нульового елемента – до останнього. Ідея
методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі
проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в
неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву, зверху розташовується самий "легкий"
елемент – звідси аналогія з бульбашкою. Наступний прохід виконується до другого
верхнього елементу, таким чином другий за величиною елемент піднімається на
правильну позицію ...
Виконуємо проходи по всій нижній частині масиву до тих пір, поки в ній не
залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність
впорядкована за зростанням.

Середнє число порівнянь і обмінів мають квадратичний порядок зростання: О(n
2
),
звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і
малоефективний. Проте, у нього є величезний плюс: він простий і його можна по-всякому
поліпшувати.
По-перше, розглянемо ситуацію, коли на якому-небудь з проходів не відбулося
жодного обміну. Що це означає? Це означає, що всі пари розташовані в правильному
порядку, так що масив вже відсортований і продовжувати процес не має сенсу (особливо,
якщо масив був відсортований з самого початку!). Отже, перше поліпшення алгоритму
полягає в запам'ятовуванні, чи проводився на даному проході будь-якої обмін. Якщо
немає – алгоритм закінчує роботу.
Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт
обміну, але і індекс
k
останнього обміну. Дійсно, всі пари сусідів елементів з індексами
меншими за k, вже розташовані в потрібному порядку. Подальші проходи можна
закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої
межі.
Якісно інше поліпшення алгоритму можна отримати з наступного спостереження.
Хоча “легка” бульбашка знизу підніметься наверх за один прохід, важкі бульбашки
опускаються з мінімальною швидкістю: один крок за ітерацію. Тому масив 2 3 4 5 6 1 буде
відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.
Щоб уникнути подібного ефекту, можна змінювати напрямок наступних проходів.
Одержаний алгоритм іноді називають "шейкер-сортуванням".
Наскільки описані зміни впливають на ефективність методу? Середня кількість
порівнянь хоч і зменшилася, але залишається O(n
2
), в той час як число обмінів
залишається незмінную. Середня (гірша) кількість операцій залишається квадратичною.
Додаткова пам'ять, очевидно, не потрібна. Поведінка вдосконаленого методу
досить природня, майже відсортований масив буде відсортований набагато швидше
випадкового. Сортування бульбашкою стійке, однак шейкер-сортування втрачає цю якість.
На практиці метод бульбашки, навіть з поліпшеннями, працює занадто повільно. Тому
майже не застосовується.