Участник:Kiryan/Алгоритм сортировки вставками

Основные авторы описания: Деревянкин К.Е.

Свойства и структура алгоритмов

Общее описание алгоритма

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Математическое описание алгоритма

Пусть задано множество: S = {x₁, x₂, ..., xₙ} ⊆ X, где (X, ≼) — линейно упорядоченное множество. Требуется найти биекцию π: {1,2,...,n} → {1,2,...,n} такую, что: x_π(1) ≼ x_π(2) ≼ ... ≼ x_π(n). Алгоритм сортировки вставками можно представить как последовательность преобразований массива A:

A⁽⁰⁾ = A

A⁽¹⁾ = INSERT(A⁽⁰⁾, 1)

A⁽²⁾ = INSERT(A⁽¹⁾, 2)

...

A^(n-1) = INSERT(A^(n-2), n-1),

где операция INSERT определяется как: INSERT(B, k) = [b₀, b₁, ..., b_j-1, b_k, b_j, ..., b_k-1, b_k+1, ..., b_m-1], где j = max{i ∈ {0,1,...,k} | ∀l < i: b_l ≼ b_k} ∪ {-1} + 1

После k-й итерации внешнего цикла (0 ≤ k ≤ n-1) выполняется:

1. Элемент маркированного списка
2. Подмассив A[0..k] отсортирован: ∀i,j ∈ {0,...,k}: i < j ⇒ A[i] ≼ A[j]

Множество элементов в A[0..k] есть перестановка исходных элементов A₀[0..k]

Вычислительное ядро алгоритма

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

Литература

Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.