Сортування вставками
[Ред] Алгоритм
Завдання полягає в наступному: є частина масиву, яка вже відсортована, і потрібно вставити інші елементи масиву в відсортовану частину, зберігши при цьому впорядкованість. Для цього на кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію в уже відсортованої частини масиву, до тих пір поки весь набір вхідних даних не буде відсортований. Метод вибору чергового елементу з початкового масиву довільний, проте зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються по порядку їх появи у вхідному масиві.
Так як в процесі роботи алгоритму можуть мінятися місцями тільки сусідні елементи, кожен обмін зменшує число інверсій на одиницю. Отже, кількість обмінів дорівнює кількості інверсій в вихідному масиві незалежно від реалізації сортування. Максимальна кількість інверсій міститься в масиві, елементи якого відсортовані по незростання. Число інверсій в такому масиві.
Алгоритм працює за, де - число обмінів елементів вхідного масиву, яка дорівнює кількості інверсій. В середньому і в гіршому випадку - за. Мінімальні оцінки зустрічаються в разі вже впорядкованої вихідної послідовності елементів, найгірші - коли вони розташовані в зворотному порядку.
[Ред] Псевдокод
[Ред] Приклад роботи
Приклад роботи алгоритму для масиву
Перший прохід (проштовхує другий елемент -2)
Алгоритм порівнює другий елемент з першим і змінює їх місцями.
Другий прохід (проштовхує третій елемент -4)
Порівнює третій з другим і міняє місцями
Другий і перший відсортовані, swap не потрібно
Третій прохід (проштовхує четвертий -3)
Змінює четвертий і третій місцями
Змінює третій і другий місцями
Другий і перший відсортовані, swap не потрібно
Четвертий прохід (проштовхує п'ятий елемент -1)
Змінює п'ятий і четвертий місцями
Змінює четвертий і третій місцями
Змінює третій і другий місцями
Змінює другий і перший місцями. Масив відсортований.
[Ред] Оптимізації
[Ред] Бінарні вставки
Тепер замість лінійного пошуку позиції ми будемо використовувати бінарний пошук. отже кількість порівнянь зміниться з до. Кількість порівнянь помітно зменшилася, але для того, щоб поставити елемент на на своє місце, все ще необхідно перемістити велику кількість елементів. В результаті час виконання алгоритму в асимптотично не зменшилася. Бінарні вставки вигідно використовувати тільки в разі коли порівняння займає багато часу в порівнянні зі зрушенням. Наприклад коли ми використовуємо масив довгих чисел.
[Ред] двоколійних вставки
Суть цього методу в тому, що замість відсортованої частини масиву ми використовуємо область виведення. Перший елемент поміщається в середину області виведення, а місце для наступних елементів звільняється шляхом зсуву елементів вліво або вправо туди, куди вигідніше. Приклад для набору елементів
Перший прохід (проштовхує другий елемент -5)
Так як в поле виведення немає елементів то ми просто додаємо елемент туди.
Другий прохід (проштовхує третій елемент -7)
За допомогою бінарного пошуку знаходимо позицію і так як позиція крайня то зрушувати нічого не доводиться.
Третій прохід (проштовхує четвертий -3)
За допомогою бінарного пошуку знаходимо позицію і так як позиція крайня то зрушувати нічого не доводиться.
Четвертий прохід (проштовхує п'ятий елемент -4)
За допомогою бінарного пошуку знаходимо позицію. Відстань до лівого краю зони виведення менше їм до правого то зрушуємо ліву частину.
Четвертий прохід (проштовхує п'ятий елемент -6)
Відстань до правого краю менше ніж до лівого, отже рухаємо праву частину.
Як можна помітити структура поля виведення має схожість з Деком. а саме ми вибираємо край до якого ближче наш елемент, потім додаємо з цього боку наш елемент і рухаємо його. Як ми бачимо в цьому прикладі знадобилося зрушити всього елемента. Завдяки тому що для вставки -ого елемента потрібно зрушень в гіршому випадку замість, то і підсумкове число необхідних операцій в гіршому випадку складе.