náhled|Grafická ukázka řazení vkládáním. Řazení vkládáním, známý jako , 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 , 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 Posloupnost rozdělíme na seřazenou a neseřazenou tak, že seřazená obsahuje první prvek posloupnosti Z neseřazené části vybereme první prvek a zařadíme jej na správné místo v seřazené posloupnosti Prvky v seřazené posloupnosti posuneme o jednu pozici doprava Seřazenou část zvětšíme o jeden prvek. Naopak neseřazenou část o jeden prvek zleva zmenšíme 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
Kategorie:Řadicí algoritmy Kategorie:Stabilní řadící algoritmy