11.4 Сортировка вставками¶
Сортировка вставками (insertion sort) - это простой алгоритм сортировки, принцип которого очень похож на ручное упорядочивание колоды карт.
Точнее говоря, в неотсортированном диапазоне выбирается опорный элемент, после чего он поочередно сравнивается с элементами слева в уже отсортированном диапазоне и вставляется в правильную позицию.
На рисунке 11-6 показан процесс вставки элемента в массив. Пусть опорный элемент обозначен как base ; нам нужно сдвинуть все элементы от целевого индекса до base на одну позицию вправо, а затем присвоить base значение в целевом индексе.
Рисунок 11-6 Одна операция вставки
11.4.1 Алгоритм¶
Общий процесс сортировки вставками показан на рисунке 11-7.
- В начальном состоянии отсортирован только первый элемент массива.
- Выбрать второй элемент массива как
base; после вставки в правильную позицию первые 2 элемента массива окажутся отсортированными. - Выбрать третий элемент как
base; после вставки в правильную позицию первые 3 элемента массива окажутся отсортированными. - Продолжать по аналогии; в последнем раунде в качестве
baseберется последний элемент, и после его вставки все элементы массива будут отсортированы.
Рисунок 11-7 Процесс сортировки вставками
Пример кода:
insertion_sort.py
def insertion_sort(nums: list[int]):
"""Сортировка вставками"""
# Внешний цикл: отсортированный диапазон [0, i-1]
for i in range(1, len(nums)):
base = nums[i]
j = i - 1
# Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while j >= 0 and nums[j] > base:
nums[j + 1] = nums[j] # Сдвинуть nums[j] на одну позицию вправо
j -= 1
nums[j + 1] = base # Поместить base в правильную позицию
insertion_sort.cpp
/* Сортировка вставками */
void insertionSort(vector<int> &nums) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (int i = 1; i < nums.size(); i++) {
int base = nums[i], j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]; // Сдвинуть nums[j] на одну позицию вправо
j--;
}
nums[j + 1] = base; // Поместить base в правильную позицию
}
}
insertion_sort.java
/* Сортировка вставками */
void insertionSort(int[] nums) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (int i = 1; i < nums.length; i++) {
int base = nums[i], j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]; // Сдвинуть nums[j] на одну позицию вправо
j--;
}
nums[j + 1] = base; // Поместить base в правильную позицию
}
}
insertion_sort.cs
/* Сортировка вставками */
void InsertionSort(int[] nums) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (int i = 1; i < nums.Length; i++) {
int bas = nums[i], j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > bas) {
nums[j + 1] = nums[j]; // Сдвинуть nums[j] на одну позицию вправо
j--;
}
nums[j + 1] = bas; // Поместить base в правильную позицию
}
}
insertion_sort.go
/* Сортировка вставками */
func insertionSort(nums []int) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for i := 1; i < len(nums); i++ {
base := nums[i]
j := i - 1
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
for j >= 0 && nums[j] > base {
nums[j+1] = nums[j] // Сдвинуть nums[j] на одну позицию вправо
j--
}
nums[j+1] = base // Поместить base в правильную позицию
}
}
insertion_sort.swift
/* Сортировка вставками */
func insertionSort(nums: inout [Int]) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for i in nums.indices.dropFirst() {
let base = nums[i]
var j = i - 1
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while j >= 0, nums[j] > base {
nums[j + 1] = nums[j] // Сдвинуть nums[j] на одну позицию вправо
j -= 1
}
nums[j + 1] = base // Поместить base в правильную позицию
}
}
insertion_sort.js
/* Сортировка вставками */
function insertionSort(nums) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (let i = 1; i < nums.length; i++) {
let base = nums[i],
j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]; // Сдвинуть nums[j] на одну позицию вправо
j--;
}
nums[j + 1] = base; // Поместить base в правильную позицию
}
}
insertion_sort.ts
/* Сортировка вставками */
function insertionSort(nums: number[]): void {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (let i = 1; i < nums.length; i++) {
const base = nums[i];
let j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]; // Сдвинуть nums[j] на одну позицию вправо
j--;
}
nums[j + 1] = base; // Поместить base в правильную позицию
}
}
insertion_sort.dart
/* Сортировка вставками */
void insertionSort(List<int> nums) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (int i = 1; i < nums.length; i++) {
int base = nums[i], j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]; // Сдвинуть nums[j] на одну позицию вправо
j--;
}
nums[j + 1] = base; // Поместить base в правильную позицию
}
}
insertion_sort.rs
/* Сортировка вставками */
fn insertion_sort(nums: &mut [i32]) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for i in 1..nums.len() {
let (base, mut j) = (nums[i], (i - 1) as i32);
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while j >= 0 && nums[j as usize] > base {
nums[(j + 1) as usize] = nums[j as usize]; // Сдвинуть nums[j] на одну позицию вправо
j -= 1;
}
nums[(j + 1) as usize] = base; // Поместить base в правильную позицию
}
}
insertion_sort.c
/* Сортировка вставками */
void insertionSort(int nums[], int size) {
// Внешний цикл: отсортированный диапазон [0, i-1]
for (int i = 1; i < size; i++) {
int base = nums[i], j = i - 1;
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
// Сдвинуть nums[j] на одну позицию вправо
nums[j + 1] = nums[j];
j--;
}
// Поместить base в правильную позицию
nums[j + 1] = base;
}
}
insertion_sort.kt
/* Сортировка вставками */
fun insertionSort(nums: IntArray) {
// Внешний цикл: отсортированные элементы равны 1, 2, ..., n
for (i in nums.indices) {
val base = nums[i]
var j = i - 1
// Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j] // Сдвинуть nums[j] на одну позицию вправо
j--
}
nums[j + 1] = base // Поместить base в правильную позицию
}
}
insertion_sort.rb
### Сортировка вставками ###
def insertion_sort(nums)
n = nums.length
# Внешний цикл: отсортированный диапазон [0, i-1]
for i in 1...n
base = nums[i]
j = i - 1
# Внутренний цикл: вставить base в правильную позицию отсортированного диапазона [0, i-1]
while j >= 0 && nums[j] > base
nums[j + 1] = nums[j] # Сдвинуть nums[j] на одну позицию вправо
j -= 1
end
nums[j + 1] = base # Поместить base в правильную позицию
end
end
Визуализация кода
11.4.2 Характеристики алгоритма¶
- Временная сложность равна \(O(n^2)\), алгоритм адаптивен: в худшем случае каждой операции вставки требуется соответственно \(n - 1\), \(n-2\), \(\dots\), \(2\), \(1\) итераций, а их сумма равна \((n - 1) n / 2\) , поэтому временная сложность равна \(O(n^2)\) . Если входные данные уже упорядочены, операция вставки завершается раньше. Когда входной массив полностью отсортирован, сортировка вставками достигает лучшей временной сложности \(O(n)\) .
- Пространственная сложность равна \(O(1)\), сортировка выполняется на месте: указатели \(i\) и \(j\) используют константный объем дополнительной памяти.
- Стабильная сортировка: в процессе вставки элементы помещаются справа от равных им элементов, поэтому их относительный порядок не меняется.
11.4.3 Преимущества сортировки вставками¶
Временная сложность сортировки вставками равна \(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)\) . Если входные данные уже частично упорядочены, сортировка вставками обычно эффективнее сортировки выбором.
- Сортировка выбором нестабильна, поэтому ее нельзя использовать для многоуровневой сортировки.