Сортировка вставками
Описание
Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки, который строит отсортированный массив по одному элементу за раз. Он работает аналогично тому, как вы сортируете игральные карты в руках — берёте по одной карте и вставляете её на правильное место среди уже отсортированных карт.
Зачем это нужно
Сортировка вставками — один из простейших алгоритмов сортировки, однако она имеет важные практические применения. Она эффективна для небольших наборов данных и почти отсортированных данных. Понимание сортировки вставками помогает освоить концепцию инкрементальной сортировки и адаптивных алгоритмов.
Визуализация
Как работает алгоритм
Сортировка вставками строит отсортированный массив по одному элементу за раз. Она берёт каждый элемент из несортированной части и вставляет его на правильную позицию в отсортированной части, сдвигая большие элементы при необходимости.
1. Начинаем с первого элемента
Первый элемент считается отсортированным сам по себе. Остальная часть массива несортированная.
2. Берём следующий элемент (ключ)
Берём первый несортированный элемент — это ваш «ключ». Сравниваем его с элементами в отсортированной части, двигаясь справа налево.
3. Сдвиг и вставка
Если ключ меньше сравниваемого элемента, сдвигаем этот элемент на одну позицию вправо. Продолжаем, пока не найдём правильную позицию для ключа:
- Сдвиг: перемещаем элементы, большие ключа, на одну позицию вправо.
- Вставка: помещаем ключ на правильную позицию в отсортированной части.
4. Повторяем, пока не отсортируем
Продолжаем брать следующий несортированный элемент и вставлять его в отсортированную часть. Когда все элементы обработаны, массив полностью отсортирован.
Берём 11, сравниваем с 12 → 11 < 12, сдвигаем 12 вправо → вставляем 11 на позицию 0. Массив: [11, 12, 13, 5, 6].
Берём 13, сравниваем с 12 → 13 > 12, остаётся. Берём 5, сдвигаем 13, 12, 11 → вставляем 5 на позицию 0. Массив: [5, 11, 12, 13, 6].
Сложность
Анализ сложности
Временная сложность
O(n) — лучший случай, когда массив уже отсортирован. Каждый элемент сравнивается только один раз со своим предшественником, что даёт один проход по массиву.
O(n²) — в среднем каждый элемент нужно сравнить примерно с половиной отсортированной части. Это даёт примерно n²/4 сравнений.
O(n²) — худший случай, когда массив отсортирован в обратном порядке. Каждый новый элемент нужно сравнить со всеми элементами отсортированной части и сдвинуть в начало.
Пространственная сложность
O(1) — сортировка вставками работает на месте, требуя только одну дополнительную переменную для хранения ключа. Дополнительные массивы не нужны.
Стабильная сортировка — равные элементы сохраняют относительный порядок. Это потому, что мы сдвигаем только элементы, большие ключа, а не равные ему.
Сортировка вставками адаптивна — она работает лучше на частично отсортированных данных. Если массив почти отсортирован, алгоритм приближается к O(n). Это делает его полезным как завершающая фаза более сложных алгоритмов, таких как сортировка Шелла или Timsort.
Пример кода
function insertionSort(arr: number[]): void {for (let i = 1; i < arr.length; i++) {const key = arr[i];let j = i - 1;// Move elements greater than key one position aheadwhile (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// Insert key at correct positionarr[j + 1] = key;}}// Usage exampleconst unsorted = [12, 11, 13, 5, 6];const sorted = [...unsorted]; // Copy to avoid mutating originalinsertionSort(sorted);console.log(sorted); // [5, 6, 11, 12, 13]
Примеры использования в реальных задачах
Сортировка небольших наборов данных
Сортировка вставками часто используется для небольших наборов данных (n < 50), где её простота и низкие накладные расходы делают её быстрее более сложных алгоритмов. Многие гибридные алгоритмы переключаются на сортировку вставками для маленьких подмассивов.
Онлайн-сортировка
Сортировка вставками может сортировать данные по мере их поступления (онлайн-алгоритм). Каждый новый элемент вставляется на правильную позицию в уже отсортированной части, что делает её идеальной для потоковых данных.
Timsort (сортировка по умолчанию в Python/Java)
Timsort, алгоритм сортировки по умолчанию в Python и Java, использует сортировку вставками для небольших серий (обычно ≤ 32 элементов). Она использует тот факт, что сортировка вставками очень эффективна для небольших, частично отсортированных данных.
Почти отсортированные данные
Когда данные уже в основном отсортированы (например, добавление нескольких новых записей в отсортированную базу данных), сортировка вставками работает почти за линейное время, что делает её оптимальным выбором.
Обучающий инструмент
Сортировка вставками часто является первым изучаемым алгоритмом сортировки благодаря интуитивной логике (сортировка карт) и простой реализации. Она помогает студентам понять концепцию инкрементальных алгоритмов.