Сортировка вставками (insertion sort) в Python
В этом уроке вы реализуете сортировку вставками, помещая каждый элемент на своё место в уже отсортированной части.
Введение
Какую задачу это решает
Данные часто приходят почти отсортированными или по одному элементу: в отсортированный список баллов добавляется один новый. Пересортировывать всё расточительно. Сортировка вставками отлично подходит для такого случая. Именно так многие раскладывают игральные карты в руке.
Пример из жизни
Сортировка вставками - это то, как сортируют карты в руке. Вы берёте по одной карте и сдвигаете её влево мимо всех больших карт, пока она не встанет на своё место. Карты слева от неё всегда упорядочены.
current = result[index]🃏 Взять следующую картуresult[position] > current👈 Карта слева больше?result[position + 1] = result[position]➡️ Сдвинуть большую карту на место вправоresult[position + 1] = current📥 Положить карту в образовавшийся промежутокСортировка вставками строит отсортированную часть по одному элементу, сдвигая большие элементы вправо и вставляя текущий в освободившееся место. В худшем случае это O(n²), а на почти отсортированных данных - почти O(n).
Главное
for index in range(1, len(result)):начинает со второго элемента; один элемент уже отсортирован.currentхранит вставляемое значение, пока большие значения сдвигаются.while position >= 0 and result[position] > current:сдвигает каждое большее значение на одно место вправо.result[position + 1] = currentкладёт значение в открывшийся промежуток.
Когда это нужно?
- Небольшие или почти отсортированные списки.
- Поддержание списка отсортированным по мере поступления новых элементов.
- Завершающий шаг в более быстрых сортировках: маленькие части они досортировывают вставками.
Когда это не нужно
- Большие случайные списки: сдвиги становятся медленными, поэтому используйте
sorted(). - Частые вставки в большой отсортированный список:
bisect.insortнаходит позицию бинарным поиском.
Визуализация: Сортировка вставками (insertion sort) в Python
O(n²)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Запись 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
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
Все задачи