Princip
- Vstupní posloupnost se rozdělí nalevou seřazenoua pravou a neseřazenou část.
- Na počátku tvoří levou část první prvek vstupní posloupnosti.
- Z neseřazené pravé části se vezme první prvek a vloží se zpravana správnou pozici v levé seřazené části.
- Po vložení prvku do seřazené části se posune hranice meziseřazenou a neseřazenou částí o jednu pozici doprava.
- To se opakuje, dokud není pravá neseřazená část prázdná.
Pseudokód
Vstup: pole P[1 … n] Výstup: vzestupně seřazené pole PAlgoritmus InsertSort
Pro i:= 1. . . n−1:
key:=P[i+ 1]
j:=i
Dokud j > 0 and P[j] s > key:
P[j+ 1] :=P[j]
j−−
P[j+ 1] :=key
Složitost
Korektně seřadí n-prvkové pole v čase O(n2) a je stabilní, in-place, datově citlivý.
Důkaz
- Invariant: Po i-té iteraci cyklu na řádcích (2)-(8) je vlevoseřazená posloupnost délky i+1 a vpravo zbývá n−1−i neseřazených prvků.
- V i-tém kroku trvá vložení prvku do levé seřazené části čas O(i) a celkově tedy O(1+···+(n−1)) = O(n2).
- V nejlepším případě má algoritmus složitost Θ(n) (případ již seřazeného pole, kdy každý prvek zůstává na svém místě)
- Díky podmínce P[j] > key na řádku (4) se stejně velké prvky při vkládání neprohazují.
Implementace v C
void insertSort(int n, int A[n]) { int value, j; for (int i=1; i < n; i++) { value = A[i]; for (j = i; j > 0 && value < A[j-1]; j--) { A[j] = A[j-1]; } A[j] = value; } }