Сортування вставками

6.1 Визначення сортування вставками.

Сортування вставками (Insertion Sort) — це алгоритм сортування, що будує відсортований масив (або список) по одному елементу за раз. Він бере кожний елемент з невідсортованої частини і вставляє його на правильне місце в відсортованій частині.

Принцип роботи:

1. Починаємо з другого елемента масиву (перший елемент вважається відсортованим).
2. Порівнюємо поточний елемент з попередніми і переміщуємо його вліво, поки не знайдемо правильне місце.
3. Повторюємо процес для всіх елементів масиву, вставляючи кожен новий елемент на правильне місце в вже відсортованій частині масиву.

Часова та просторову складність сортування вставками

Часова складність:

• У гіршому випадку: O(n^2) — відбувається, коли елементи спочатку упорядковані в зворотньому порядку.
• У середньому випадку: O(n^2) — відбувається для випадкового розташування елементів.
• У найкращому випадку: O(n) — коли елементи вже відсортовані.

Просторова складність:

O(1) — так як алгоритм використовує постійну кількість додаткової пам'яті (лише кілька змінних для зберігання тимчасових значень).

6.2 Розбір роботи алгоритму.

На черговому кроці алгоритму маємо таку ситуацію:

• У нас є поточний елемент з індексом i.
• Усі елементи зліва від нього вже відсортовані від меншого до більшого
• Ми намагаємося вставити наш поточний елемент в відсортовану частину масиву так, щоб порядок сортування не порушився.

Спроба вставити елемент в відсортовану частину масиву виглядає так:

1. Змінна j в циклі приймає значення від i - 1 до 0.
2. Якщо поточний (i-й) елемент менший за j-й, то ми зсуваємо значення j-го елемента на 1 вправо.

Приклад: поточна ситуація:

• Зеленим зазначені вже відсортовані елементи
• Рожевим — елементи, які ще не відсортовані
• Поточний елемент під індексом 5 — зазначений коричневим.

Ми пробуємо знайти правильне місце нашому поточному елементу в відсортованій частині масиву.

Крок 1 — запам'ятовуємо значення поточного елемента в змінну Key

Крок 2 — елемент No4 більше key? (10 більше 5 ?) Тоді рухаємо елемент No4 вправо:

Крок 3 — елемент No3 більше key? (8 більше 5 ?) Тоді рухаємо елемент No3 вправо:

Крок 4 — елемент No2 більше key? (6 більше 5 ?) Тоді рухаємо елемент No2 вправо:

Крок 5 — елемент No1 більше key? (4 більше 5 ?) Ні. Тоді зберігаємо елемент KEY туди, де був елемент No2

Після того як ми вставили елемент No5 в потрібне місце, ми перемикаємося на елемент No6 і пробуємо знайти йому місце в відсортованій частині масиву:

Потім беремо сьомий елемент:

Потім 8-й

6.3 Реалізація алгоритму сортування вставками.

Ось як цей алгоритм виглядатиме на Python:

def insertion_sort(arr):
    # Проходимо по всіх елементах масиву, починаючи з другого
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # Переміщуємо елементи arr[0..i - 1], які більші за ключ, на одну позицію вперед while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
    arr[j + 1] = key # Вставляємо ключ на правильне місце
        
# Приклад використання:
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Відсортований масив:", arr)
        

Пояснення:

• Зберігаємо поточний елемент в Key
• Зсуваємо всі елементи відсортованої частини масиву вправо
• Вставляємо наш елемент в підходяще місце

Приклад роботи алгоритму

Візьмемо приклад масиву: [12, 11, 13, 5, 6]

1. Перший прохід (i = 1):

• Порівнюємо 11 і 12, переміщуємо 12 вправо.
• Масив: [11, 12, 13, 5, 6]

2. Другий прохід (i = 2):

• 13 вже на своєму місці.
• Масив: [11, 12, 13, 5, 6]

3. Третій прохід (i = 3):

• Порівнюємо 5 з 13, 12, та 11, переміщуємо всі вправо.
• Масив: [5, 11, 12, 13, 6]

4. Четвертий прохід (i = 4):

• Порівнюємо 6 з 13, 12, та 11, переміщуємо всі вправо.
• Масив: [5, 6, 11, 12, 13]

Алгоритм завершується, так як усі елементи відсортовані.