Існує кілька основних алгоритмів розв’язання задачі сортування масиву. Один з найбільш відомих серед них – сортування вставками. В силу своєї наочності та простоти, але малої ефективності, цей метод використовується в основному при навчанні програмуванню. Він дозволяє розібратися в основних механізмах сортування.
Опис алгоритму
Суть алгоритму сортування вставками полягає в тому, що всередині вихідного масиву формується впорядкований потрібним чином сегмент. Кожен елемент по одному порівнюється з перевіреною частиною і вставляється на належне місце. Таким чином, після перебору всіх елементів вони шикуються в правильному порядку.
Черговість вибору елементів може бути будь-який, вони можуть відбиратися довільно або згідно з алгоритмом. Найчастіше використовується послідовний перебір з початку масиву, де і формується впорядкований сегмент.
Початок сортування може виглядати наступним чином:
І так далі до кінця початкового масиву.
Сортування вставками в реальному житті
Для наочності варто навести приклад того, як використовується цей механізм сортування в звичайному житті.
Візьмемо, наприклад, гаманець. У відділенні для банкнот лежать у безладі сотенні, п’ятисотенні і тисячні купюри. Це непорядок, у такій мішанині складно відразу знайти потрібний папірець. Масив купюр необхідно відсортувати.
Найпершою йде банкнота номіналом 1000 рублів, а відразу за нею – 100. Беремо полковосотенну та розміщуємо її попереду. Третя за рахунком – 500 рублів, законне місце для неї – між сотнею і тисячею.
Таким же чином ми відсортуємо отримані карти при грі в “Дурня”, щоб було простіше орієнтуватися в них.
Оператори та допоміжні функції
Метод сортування вставками приймає на вхід вихідний масив, який слід упорядкувати, функцію порівняння і при необхідності функцію, що визначає правило перебору елементів. Найчастіше замість неї використовується звичайний оператор циклу.
Перший елемент сам по собі є впорядкованим безліччю, тому порівняння починається з другого.
В алгоритмі часто застосовується допоміжна функція для обміну двох значень (swap). Вона використовує додаткову тимчасову змінну, що вимагає витрат пам’яті і трохи уповільнює роботу коду.
Альтернативою є масове зміщення групи елементів і подальша вставка поточного на звільнене місце. При цьому перехід до наступного елемента відбувається тоді, коли порівняння видала позитивний результат, що свідчить про правильному порядку.
Приклади реалізації
Конкретна реалізація багато в чому залежить від використовуваної мови програмування, його синтаксису і структур.
Класична реалізація на мові C з використанням тимчасової змінної для обміну значень:
int i, j, temp;
for (i = 1; i = 0; j–)
{
if (array[j] < temp)
break;
array[j + 1] = array[j];
array[j] = temp;
}
}
Реалізація на PHP:
function insertion_sort(&$a) {
for ($i = 1; $i = 0 && $a[$j] > $x; $j–) {
$a[$j + 1] = $a[$j];
}
$a[$j + 1] = $x;
}
}
Тут спочатку відбувається зсув вправо всіх елементів, що відповідають умові сортування, а потім поточний елемент вставляється на звільнене місце.
Код Java з використанням циклу while:
public static void insertionSort(int[] arr) {
for(int i = 1; i = 0 && arr[prevKey] > currElem){
arr[prevKey+1] = arr[prevKey];
arr[prevKey] = currElem;
prevKey–;
}
}
}
Загальний сенс коду залишається незмінним: кожен елемент масиву послідовно порівнюється з попередніми і змінюється з ними місцями при необхідності.
Оцінка часу роботи
Очевидно, що в найкращому випадку на вході алгоритму буде вже впорядкований правильним чином масив. У цій ситуації алгоритмом доведеться просто перевірити кожний елемент, щоб переконатися, що він стоїть на своєму місці, не здійснюючи обмінів. Таким чином, час роботи буде прямо залежати від довжини вихідного масиву O(n).
Найгірший випадок вхідних даних – масив, відсортований у порядку, зворотному до потрібного. Тут потрібна велика кількість перестановок, функція часу виконання буде залежати від кількості елементів, зведеного в квадрат.
Точна кількість перестановок для абсолютно неупорядкованого масиву можна обчислити за формулою:
n*(n-1)/2
, де n – довжина вихідного масиву. Таким чином, для розстановки 100 елементів у правильному порядку потрібно 4950 перестановок.
Метод вставок дуже ефективний для сортування невеликих або частково впорядкованих масивів. Однак повсюдно застосовувати його не рекомендується із-за високої складності обчислень.
Алгоритм використовується як допоміжний у багатьох інших більш складних методах сортування.
Сортування однакових значень
Алгоритм вставок відноситься до так званих стійким сортувань. Це означає, що він не міняє місцями однакові елементи, а зберігає їх вихідний порядок. Показник стійкості у багатьох випадках важливий для правильного упорядкування.
Вище представлений чудовий наочний приклад сортування вставками в танці.
