Слайд 4
🧩 Сортировка простыми вставками (Insertion Sort)
Алгоритм сортировки простыми вставками делит список на две части: отсортированную и неотсортированную. Из неотсортированной части по одному извлекаются элементы и вставляются в нужное место в отсортированной части. Этот процесс повторяется, пока все элементы не окажутся упорядочены.
💡 Алгоритм эффективен, когда список уже частично отсортирован и содержит немного элементов (до 10).
В таких случаях он может быть быстрее даже некоторых «умных» сортировок.
🔹 Пример: сортировка a = [5, 1, 8, 2, 4] по возрастанию
Первый проход:
Делим список на части: отсортированная [5], неотсортированная [1, 8, 2, 4].
Извлекаем элемент 1 и вставляем его перед 5:
[1, 5, 8, 2, 4]Второй проход:
Отсортированная часть: [1, 5], неотсортированная: [8, 2, 4].
Извлекаем 8 — оно уже на своём месте:
[1, 5, 8, 2, 4]Третий проход:
Отсортированная часть: [1, 5, 8], неотсортированная: [2, 4].
Извлекаем 2 и вставляем его между 1 и 5:
[1, 2, 5, 8, 4]Четвёртый проход:
Отсортированная часть: [1, 2, 5, 8], неотсортированная: [4].
Извлекаем 4 и вставляем его между 2 и 5:
[1, 2, 4, 5, 8]
✅ Теперь список полностью отсортирован.
💻 Реализация на Python
a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6, 8, -2, 99]
n = len(a)
for i in range(1, n):
item = a[i] # элемент для вставки
j = i - 1
while j >= 0 and a[j] > item: # сдвигаем элементы вправо, пока не найдём место
a[j + 1] = a[j]
j -= 1
a[j + 1] = item # вставляем элемент на нужное место
print('Отсортированный список:', a)
Результат:
Отсортированный список: [-67, -3, -2, 0, 1, 6, 7, 8, 9, 12, 34, 45, 99, 1000]⚙️ Как работает алгоритм
- Сначала считается, что первый элемент уже отсортирован.
- Далее каждый следующий элемент вставляется в правильную позицию среди предыдущих.
- На каждом шаге отсортированная часть списка увеличивается на один элемент.
⚡ Время работы алгоритма:
O(n²) в худшем случае,
но в случае почти отсортированных данных — близко к O(n).
Поэтому его часто применяют в реальных алгоритмах для «досортировки» небольших массивов.