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

Незалежно від номера поточного кроку i, послідовність a[0]...a[i] є впорядкованою.
Таким чином, на (n-2)-му кроці вся послідовність, крім a[n-1] виявляється відсортованої, а
a[n-1] стоїть на останньому місці по праву (всі менші елементи вже розміщені звліва.
Для знаходження найменшого елемента з n елементів, необхідно зробити n-1
порівнянь. З урахуванням того, що кількість аналізованих елементів на кожному кроці
зменшується на одиницю, загальна кількість операцій:
(n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n
2
+n ) = О(n
2
).
Таким чином, оскільки число обмінів завжди буде меншою за кількість порівнянь,
час сортування зростає квадратично щодо кількості елементів.
Алгоритм не використовує додаткову пам'ять (всі операції відбуваються "на місці").
Чи стійкий цей метод? Розглянемо послідовність з трьох елементів, кожен з яких
має два поля, а сортування йде за першою з них.
Результат сортування можна побачити вже після кроку 0, так як більше обмінів не
буде. Порядок ключів 2a, 2b був змінений на 2b, 2a, так що метод нестійкий.
Якщо вхідна послідовність майже впорядкована, то порівнянь буде стільки ж,
значить алгоритм поводиться неприродно.
3. Сортування вставками
Сортування простими вставками в чомусь схожа на вищевикладені методи.
Аналогічним чином виконуються проходи по частині масиву та аналогічним же
чином на початку масиву "виростає" відсортована послідовність. Однак в сортуванні
бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a[0]... a[i]
стоять на правильних місцях і нікуди більш не перемістяться. Тут же подібне твердження
буде більш слабким: послідовність a[0] ... a[i] впорядкована, але при цьому по ходу
алгоритму в неї будуть вставлятися нові елементи.
Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося
вище, послідовність до цього моменту розділена на дві частини: готову a [0] ... a [i] і
невпорядковану a [i + 1] ... a [n].
На наступному, (i + 1)-м кожному кроці алгоритму, беремо a[i + 1] і вставляємо на
потрібне місце в готову частину масиву.
Пошук відповідного місця для чергового елемента вхідної послідовності
здійснюється шляхом послідовних порівнянь з елементом, що стоїть перед ним. Залежно
від результату порівняння елемент або залишається на поточному місці (вставка
завершена), або вони міняються місцями і процес повторюється.

Таким чином, в процесі вставки ми "просіюємо" елемент x до початку масиву,
зупиняючись в разі, коли:
1. Знайдено елемент, менший x або ...
2. Досягнуто початок послідовності.
Аналогічно сортуванні вибором, середнє, а також гірше число порівнянь і
пересилань оцінюються як О (n
2
), додаткова пам'ять при цьому не використовується.
Хорошим показником сортування є дуже природна поведінка: майже
відсортований масив буде відсортован дуже швидко. Це, вкупі зі стійкістю алгоритму,
робить метод хорошим вибором в відповідних ситуаціях.
Алгоритм можна злегка поліпшити. Зауважимо, що на кожному кроці
внутрішнього циклу перевіряються 2 умови. Можна об'єднати їх в одне, поставивши в
початок масиву спеціальний сторожовий елемент. Він повинен бути свідомо менше всіх
інших елементів масиву.
Тоді при j=0 буде наперед вірно a[0] <= x. Цикл зупиниться на нульовому елементі,
що і було метою умови j>=0.
Таким чином, сортування відбуватиметься правильним чином, а у внутрішньому
циклі стане на одне порівняння менше. З урахуванням того, що воно проводилося О(n
2
)
раз, то це – реальна перевага. Однак, відсортований масив буде не повний, так як з нього
зникло перше число. Для закінчення сортування це число слід повернути назад, а потім
вставити в відсортовану послідовність a[1]...a[n].
Зображений нижче графік ілюструє різницю в ефективності декількох алгоритмів
сортування.


коричнева лінія – сортування бульбашкою;

синя лінія – шейкер-сортування;

рожева лінія – сортування вибором;

жовта лінія – сортування вставками;

блакитна лінія – сортування вставками зі сторожовим
елементом;

фіолетова лінія – сортування Шелла.

жүктеу/скачать 201,91 Kb.

Достарыңызбен бөлісу: