Řazení vkládáním

Grafická ukázka řazení vkládáním.

Řazení vkládáním, známý jako insertion sort, je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus řazení vkládáním 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 rychlé řazení nebo řazení slučováním, 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ů (řazení výběrem, bublinkové řazení), 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

razeniVkladanim(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];
           A[j] = hodnota;
           j--;

Externí odkazy

• Obrázky, zvuky či videa k tématu insertion sort na Wikimedia Commons