Бинарные вставки

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

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

Но ведь отсортированная часть массива уже упорядочена. Почему бы не использовать для поиска позиции бинарный поиск?

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

1. Массив делим на отсортированную и неотсортированную части.
2. Для очередного элемента из неотсортированной части с помощью бинарного поиска находим позицию для вставки в отсортированную часть.
3. Сдвигаем элементы вправо и вставляем новый элемент.
4. Повторяем для всех элементов.

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

import bisect

def binary_insertion_sort(arr):
    """Сортировка вставками с бинарным поиском (список Python)"""
    for i in range(1, len(arr)):
        # Берём текущий элемент
        key = arr[i]
        # Находим позицию для вставки в отсортированной части arr[:i]
        pos = bisect.bisect_left(arr, key, 0, i)
        # Вставляем key на нужное место
        arr = arr[:pos] + [key] + arr[pos:i] + arr[i+1:]
    return arr

# Пример
data = [5, 2, 9, 1, 6, 3]
print(binary_insertion_sort(data))  # [1, 2, 3, 5, 6, 9]

Реализация на NumPy

import numpy as np

def binary_insertion_sort_numpy(arr):
    """Сортировка вставками с бинарным поиском (numpy.array)"""
    arr = arr.copy()  # чтобы не менять исходный массив
    for i in range(1, len(arr)):
        key = arr[i]
        # бинарный поиск позиции
        pos = np.searchsorted(arr[:i], key)
        # сдвигаем и вставляем
        arr[pos+1:i+1] = arr[pos:i]
        arr[pos] = key
    return arr

# Пример
data_np = np.array([5, 2, 9, 1, 6, 3])
print(binary_insertion_sort_numpy(data_np))  # [1 2 3 5 6 9]

Вывод

• Бинарные вставки — это улучшенная версия сортировки вставками.
• Сложность всё равно O(n²) из-за сдвигов, но поиск позиции работает быстрее.