Cesko.wiki Řazení vkládáním
Author
Albert FloresŘazení vkládáním je algoritmus, který slouží k uspořádání prvků v seznamu. Jedná se o efektivní a jednoduchý způsob, jak setřídit prvky podle jejich hodnoty. Algoritmus pracuje tak, že postupně vkládá jednotlivé prvky na správnou pozici v již seřazené části seznamu. Řazení vkládáním je poměrně účinné pro malé seznamy, kde je počet prvků omezený. Na druhou stranu je však nevhodné pro velké seznamy kvůli vysoké složitosti a dlouhému časovému nároku. Principem algoritmu je, že se postupně prochází seznam a vkládá se každý prvek na správnou pozici. Tím se vytváří seřazená část seznamu po každém vložení nového prvku. V praxi to znamená, že se prvky porovnávají s předchozími prvky a vkládají se na správné místo, dokud není seznam úplně seřazený. Algoritmus řazení vkládáním je relativně snadno implementovatelný a srozumitelný. Je však potřeba dávat pozor na správnou implementaci a efektivní využití paměti, aby se minimalizovala složitost algoritmu. Řazení vkládáním je jedním z základních řadicích algoritmů, který je vyučován na algoritmizaci a datových strukturách.
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 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
# 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--;