Řazení vkládáním

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
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[editovat | editovat zdroj]

  • 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 | editovat zdroj]

  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 | editovat zdroj]

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 | editovat zdroj]