Insertion sort

Insertion sort v akci na několika náhodných číslech

Insertion sort (neboli řazení vkládáním) je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus Insertion Sort pracuje tak, že prochází prvky postupně a každý další nesetříděný prvek zařadí na správné místo do již setříděné posloupnosti.

Je to jeden z nejrychlejších algoritmů s kvadratickou časovou složitostí. Je asymptoticky pomalejší než pokročilé algoritmy jako třeba quicksort nebo mergesort, ale má jiné výhody.

Výhody

• jednoduchá implementace
• efektivní na malých množinách
• efektivní na částečně seřazených množinách (běží v čase $O(N + d)$, kde $d$ je počet transpozic prvků množiny)
• efektivnější než většina ostatních $O(N^2)$ algoritmů (selection sort, bubble sort), průměrný čas je $\frac{N^2}{4}$ a v nejlepším případě je dokonce lineární
• řadí stabilně (nemění vzájemné pořadí prvků se stejnými klíči)
• vyžaduje pouze $O(1)$ paměti (kromě vlastního vstupu)
• je online algoritmem, tzn. dokáže řadit data tak, jak přicházejí na vstup

Princip

1. Posloupnost rozdělíme na seřazenou a neseřazenou tak, že seřazená obsahuje první prvek posloupnosti
2. Z neseřazené části vybereme první prvek a zařadíme jej na správné místo v seřazené posloupnosti
3. Prvky v seřazené posloupnosti posuneme o jednu pozici doprava
4. Seřazenou část zvětšíme o jeden prvek. Naopak neseřazenou část o jeden prvek zleva zmenšíme
5. Kroky 2-5 aplikujeme až do úplného seřazení neseřazené části

Algoritmus

insertionSort(A)
   pro i od 1 do počtu prvků opakuj:
       hodnota = A[i];
       j = i-1;
       pokud j >= 0 a zároveň A[j] > hodnota opakuj:
           A[j+1] = A[j];
           j = j--;
       A[j+1] = hodnota;