Алгоритмы на Python

Сортировка вставками (insertion sort) в Python

В этом уроке вы реализуете сортировку вставками, помещая каждый элемент на своё место в уже отсортированной части.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Данные часто приходят почти отсортированными или по одному элементу: в отсортированный список баллов добавляется один новый. Пересортировывать всё расточительно. Сортировка вставками отлично подходит для такого случая. Именно так многие раскладывают игральные карты в руке.

Пример из жизни

Сортировка вставками - это то, как сортируют карты в руке. Вы берёте по одной карте и сдвигаете её влево мимо всех больших карт, пока она не встанет на своё место. Карты слева от неё всегда упорядочены.

От сортировки карт к коду
current = result[index]🃏 Взять следующую карту
result[position] > current👈 Карта слева больше?
result[position + 1] = result[position]➡️ Сдвинуть большую карту на место вправо
result[position + 1] = current📥 Положить карту в образовавшийся промежуток
Левая часть всегда отсортирована; каждый новый элемент вставляется в неё.
Одним предложением

Сортировка вставками строит отсортированную часть по одному элементу, сдвигая большие элементы вправо и вставляя текущий в освободившееся место. В худшем случае это O(n²), а на почти отсортированных данных - почти O(n).

Главное

  1. for index in range(1, len(result)): начинает со второго элемента; один элемент уже отсортирован.
  2. current хранит вставляемое значение, пока большие значения сдвигаются.
  3. while position >= 0 and result[position] > current: сдвигает каждое большее значение на одно место вправо.
  4. result[position + 1] = current кладёт значение в открывшийся промежуток.

Когда это нужно?

  • Небольшие или почти отсортированные списки.
  • Поддержание списка отсортированным по мере поступления новых элементов.
  • Завершающий шаг в более быстрых сортировках: маленькие части они досортировывают вставками.

Когда это не нужно

  • Большие случайные списки: сдвиги становятся медленными, поэтому используйте sorted().
  • Частые вставки в большой отсортированный список: bisect.insort находит позицию бинарным поиском.

Визуализация: Сортировка вставками (insertion sort) в Python

O(n²)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
Получить кнопку запуска для этого примера

Результат выполнения

[1, 3, 4, 5, 9]

Разбор кода

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

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Запись current обратно внутри цикла

Значение нужно поставить один раз, после того как сдвинулись все большие значения.

Ошибка
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Исправление
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи