Сортування вставками в реальному житті
Для наочності варто навести приклад того, як використовується цей механізм сортування в звичайному житті.
Візьмемо, наприклад, гаманець. У відділенні для банкнот лежать у безладі сотенні, п’ятисотенні і тисячні купюри. Це непорядок, у такій мішанині складно відразу знайти потрібний папірець. Масив купюр необхідно відсортувати.
Найпершою йде банкнота номіналом 1000 рублів, а відразу за нею – 100. Беремо полковосотенну та розміщуємо її попереду. Третя за рахунком – 500 рублів, законне місце для неї – між сотнею і тисячею.
Таким же чином ми відсортуємо отримані карти при грі в “Дурня”, щоб було простіше орієнтуватися в них.
Оператори та допоміжні функції
Метод сортування вставками приймає на вхід вихідний масив, який слід упорядкувати, функцію порівняння і при необхідності функцію, що визначає правило перебору елементів. Найчастіше замість неї використовується звичайний оператор циклу.
Перший елемент сам по собі є впорядкованим безліччю, тому порівняння починається з другого.
В алгоритмі часто застосовується допоміжна функція для обміну двох значень (swap). Вона використовує додаткову тимчасову змінну, що вимагає витрат пам’яті і трохи уповільнює роботу коду.
Альтернативою є масове зміщення групи елементів і подальша вставка поточного на звільнене місце. При цьому перехід до наступного елемента відбувається тоді, коли порівняння видала позитивний результат, що свідчить про правильному порядку.
