Insertion Sort
Insertion Sort — алгоритм, который строит отсортированную часть массива, вставляя элементы по одному.
Основная идея
Берём очередной элемент и вставляем его в нужное место среди уже отсортированных.
Пошаговый пример
Исходный массив:
[7, 4, 5, 2, 9]- Берём 4 и вставляем перед 7 → [4, 7, 5, 2, 9]
- Берём 5 и вставляем между 4 и 7 → [4, 5, 7, 2, 9]
- Берём 2 и сдвигаем элементы вправо → [2, 4, 5, 7, 9]
Псевдокод
for i from 1 to n - 1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
Оптимизация: Эффективен на почти отсортированных данных.
Сложность
Время
O(n²) в среднем/худшем, O(n) в лучшем случае.
Память
O(1), in-place.
Когда используется
- Маленькие массивы
- Почти отсортированные данные
- База для гибридных сортировок
Ключевые свойства
- Стабильный
- In-place
- Простой для понимания