Insert Sort

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 P
Algoritmus 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;
    }
}

Celý kód ke stažení zde.

Související