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

Сортировка вставками — ещё один простой квадратичный алгоритм.

Название подсказывает его суть: мы берём элементы по одному и вставляем их в правильное место в уже упорядоченной части массива.

Идея алгоритма

Представим, что у нас есть две части массива:

левая — уже отсортированная,
правая — ещё не отсортированная.

На старте в отсортированной части находится только первый элемент (массив из одного элемента всегда отсортирован).
Берём следующий элемент из правой части и находим для него подходящее место в левой, чтобы порядок не нарушился.
Для этого мы «сдвигаем» элементы влево или вправо, пока не освободим правильное место.
Повторяем шаги, пока правая часть не станет пустой.

Пример (ручной)

Возьмём массив:

[5, 3, 4, 1, 2]

Считаем, что [5] отсортирован. Берём 3, вставляем его слева от 5:

[3, 5, 4, 1, 2]

Берём 4, вставляем между 3 и 5:

[3, 4, 5, 1, 2]

Берём 1, вставляем в самое начало:

[1, 3, 4, 5, 2]

Берём 2, вставляем между 1 и 3:

[1, 2, 3, 4, 5]

Сложность алгоритма

В худшем случае (массив изначально отсортирован в обратном порядке) для каждого элемента придётся просматривать почти всю левую часть.
Тогда время работы составит O(n²).
В лучшем случае (массив уже отсортирован) сортировка вставками работает за O(n), потому что новые элементы сразу «становятся на место».

Реализация на Python (список)

def insertion_sort(arr):
    """Сортировка вставками для списка Python"""
    for i in range(1, len(arr)):
        temp = arr[i]   # Текущий элемент, который нужно вставить
        j = i - 1
        # Сдвигаем элементы вправо, пока они больше temp
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        # Вставляем элемент на найденное место
        arr[j + 1] = temp

# Пример
nums = [5, 3, 4, 1, 2]
insertion_sort(nums)
print(nums)  # [1, 2, 3, 4, 5]

Вариант для NumPy

import numpy as np

def insertion_sort_numpy(arr):
    """Сортировка вставками для numpy.array"""
    arr = arr.copy()
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp
    return arr

# Пример
data = np.array([5, 3, 4, 1, 2])
print(insertion_sort_numpy(data))  # [1 2 3 4 5]

Сравнение с пузырьковой сортировкой

На первый взгляд, сортировка вставками похожа на пузырьковую:

в обоих алгоритмах используются вложенные циклы,
сложность одинаковая — O(n²).

Но есть ключевое отличие:

в пузырьке элементы «всплывают» через обмены,
во вставках мы ищем правильное место для элемента и вставляем его туда.

Итог

Сортировка вставками — ещё один классический квадратичный алгоритм.

Она:

проста в реализации,
работает быстрее пузырька на почти отсортированных данных,
но в среднем также требует O(n²) операций.

На практике её иногда используют для небольших массивов или в комбинации с более быстрыми сортировками (например, внутри сортировки слиянием).

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