Ř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.

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

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

editovat
  • jednoduchá implementace
  • efektivní na malých množinách
  • efektivní na částečně seřazených množinách (běží v čase  , kde   je počet transpozic prvků množiny)
  • efektivnější než většina ostatních   algoritmů (řazení výběrem, bublinkové řazení), průměrný čas je   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   paměti (kromě vlastního vstupu)
  • je online algoritmem, tzn. dokáže řadit data tak, jak přicházejí na vstup

Princip

editovat
  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

editovat
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

editovat