Сортировка вставками

Сортировка вставками (insertion sort) - это простой алгоритм сортировки, принцип которого очень похож на ручную сортировку карт в колоде.

Точнее говоря, в неотсортированном диапазоне выбирается опорный элемент, после чего он сравнивается с элементами слева в уже отсортированном диапазоне и вставляется в правильную позицию.

На рисунке ниже показан процесс вставки элемента в массив. Пусть опорный элемент обозначен как base. Нам нужно сдвинуть все элементы от целевого индекса до base на одну позицию вправо, а затем записать base в целевой индекс.

Алгоритм

Общий процесс сортировки вставками показан на рисунке ниже.

1. В начальном состоянии отсортирован только первый элемент массива.
2. Выбрать второй элемент массива как base. После вставки в правильную позицию первые два элемента массива окажутся отсортированными.
3. Выбрать третий элемент как base. После вставки в правильную позицию первые три элемента массива окажутся отсортированными.
4. Продолжать по аналогии. В последнем раунде в качестве base берется последний элемент, и после его вставки все элементы массива будут отсортированы.

Пример кода:

[file]{insertion_sort}-[class]{}-[func]{insertion_sort}

Характеристики алгоритма

• Временная сложность равна \(O(n^2)\), алгоритм адаптивен: в худшем случае каждой операции вставки требуется соответственно \(n - 1\), \(n-2\), \(\dots\), \(2\), \(1\) итераций, а их сумма равна \((n - 1) n / 2\) , поэтому временная сложность равна \(O(n^2)\) . Если входные данные уже упорядочены, операция вставки завершается раньше. Когда входной массив полностью отсортирован, сортировка вставками достигает лучшей временной сложности \(O(n)\) .
• Пространственная сложность равна \(O(1)\), сортировка выполняется на месте: указатели \(i\) и \(j\) используют константный объем дополнительной памяти.
• Стабильная сортировка: в процессе вставки элементы помещаются справа от равных им элементов, поэтому их относительный порядок не меняется.

Преимущества сортировки вставками

Временная сложность сортировки вставками равна \(O(n^2)\) , а у быстрой сортировки, которую мы скоро изучим, временная сложность равна \(O(n \log n)\) . Несмотря на более высокую асимптотическую сложность, на малых объемах данных сортировка вставками обычно работает быстрее.

Этот вывод похож на сравнение линейного и двоичного поиска. Алгоритмы уровня \(O(n \log n)\) , такие как быстрая сортировка, относятся к алгоритмам на основе стратегии «разделяй и властвуй» и обычно включают больше элементарных вычислений. Когда объем данных мал, значения \(n^2\) и \(n \log n\) близки друг к другу, поэтому асимптотика не доминирует, а решающим становится число элементарных операций в каждом раунде.

На практике встроенные функции сортировки во многих языках программирования (например, в Java) используют сортировку вставками. Общая идея такова: для длинных массивов применять алгоритмы сортировки на основе стратегии «разделяй и властвуй», например быструю сортировку. Для коротких массивов сразу использовать сортировку вставками.

Хотя сортировка пузырьком, выбором и вставками имеют одинаковую временную сложность \(O(n^2)\) , в реальных задачах сортировка вставками используется заметно чаще, чем сортировка пузырьком и сортировка выбором. Основные причины таковы.

• Сортировка пузырьком основана на обмене элементов, для чего нужна временная переменная и суммарно выполняются 3 элементарные операции. Сортировка вставками основана на присваивании элементов и требует всего 1 элементарной операции. Поэтому вычислительные затраты сортировки пузырьком обычно выше, чем у сортировки вставками.
• Временная сложность сортировки выбором в любом случае равна \(O(n^2)\) . Если входные данные уже частично упорядочены, сортировка вставками обычно эффективнее сортировки выбором.
• Сортировка выбором нестабильна, поэтому ее нельзя использовать для многоуровневой сортировки.