Сортировка вставками: алгоритм и примеры реализации

Сортировка вставками — это простой алгоритм сортировки, который строит окончательный отсортированный массив по одному элементу за раз. Он эффективен для небольших наборов данных и часто используется как часть более сложных алгоритмов.

Как работает сортировка вставками

Алгоритм можно сравнить с тем, как человек сортирует карты в руке:

1. Начинаем со второго элемента массива (индекс 1)
2. Сравниваем текущий элемент с предыдущими
3. Сдвигаем элементы, которые больше текущего, вправо
4. Вставляем текущий элемент в правильную позицию
5. Повторяем процесс для всех элементов массива

Пример реализации на Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

Анализ сложности

• Лучший случай (уже отсортированный массив): O(n)
• Средний и худший случай: O(n²)
• Пространственная сложность: O(1) (сортировка на месте)

Преимущества и недостатки

Оптимизации алгоритма

Существует несколько способов улучшить производительность сортировки вставками:

1. Бинарный поиск для нахождения позиции вставки
2. Использование сортировки Шелла (модификация с разными интервалами)
3. Комбинирование с другими алгоритмами (например, Timsort)

Применение на практике

Сортировка вставками часто используется:

• В стандартных библиотеках языков для небольших массивов
• В алгоритмах сортировки файлов большого размера
• В графических процессорах благодаря своей простоте
• В системах реального времени с ограниченными ресурсами