Сортировка вставками

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 # Вставляем ключ на правильное место
    return arr  # Возвращаем отсортированный массив
        
# Пример использования:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Отсортированный массив:", sorted_arr)
# Вывод: Отсортированный массив: [5, 6, 11, 12, 13]

Объяснение:

• Сохраняем текущий элемент в 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]

Алгоритм завершается, так как все элементы отсортированы.