Сортировка вставками
Строит отсортированную последовательность, по одному добавляя элементы на нужные позиции.
Идея алгоритма
Мы последовательно берём элементы массива (как карты из колоды) и вставляем их в уже отсортированную часть слева так, чтобы порядок сохранялся. Для вставки элементы сдвигаются вправо, пока не найдётся подходящее место.
Асимптотика:
- Время (худший / средний случай): O(n²)
- Время (лучший случай — почти отсортированный массив): O(n)
- Память: O(1)
- Стабильная сортировка
Когда использовать
- Маленькие массивы;
- Почти отсортированные данные;
- Как «база» для гибридных алгоритмов (например, в быстрой сортировке для маленьких подмассивов).
Плюсы
- Очень хорошо работает на почти отсортированных массивах;
- Простая реализация;
- Стабильная сортировка.
Минусы
- Квадратичное время в худшем случае;
- Подходит только для относительно небольших массивов;
- Много сдвигов элементов при «плохом» порядке данных.
Пример кода
function insertionSort(arr) {
const a = [...arr];
const n = a.length;
for (let i = 1; i < n; i++) {
const current = a[i];
let j = i - 1;
while (j >= 0 && a[j] > current) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = current;
}
return a;
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания