Pro řešení problému řazení pole existuje několik základních algoritmů. Jedním z nejznámějších z nich je vkládání řazení. Pro svou přehlednost a jednoduchost, avšak nízkou účinnost je tato metoda využívána především ve výuce programování. Umožňuje vám porozumět základním mechanismům třídění.
Popis algoritmu
Podstatou algoritmu řazení vložení je, že uvnitř počátečního pole se vytvoří správně uspořádaný segment. Každý prvek je porovnán jeden po druhém se zaškrtnutým dílem a vložen na správné místo. Po iteraci všech prvků se tedy seřadí ve správném pořadí.
Pořadí výběru prvků může být libovolné, lze je vybrat libovolně nebo podle nějakého algoritmu. Nejčastěji se používá sekvenční výčet od začátku pole, kde se vytvoří uspořádaný segment.
Začátek třídění může vypadat takto:
- Vezměte první prvek pole.
- Vzhledem k tomu, že není s čím srovnávat, vezměte samotný prvek podle objednávkysekvence.
- Přejděte na druhou položku.
- Porovnejte jej s prvním na základě pravidla řazení.
- V případě potřeby vyměňte prvky na místech.
- Vezměte první dva prvky jako uspořádanou sekvenci.
- Přejděte na třetí položku.
- Porovnejte s druhým, v případě potřeby vyměňte.
- Pokud dojde k výměně, porovnejte ji s první.
- Vezměte tři prvky jako uspořádanou sekvenci.
A tak dále až do konce původního pole.
Řazení vkládání ze skutečného života
Pro názornost stojí za to uvést příklad toho, jak se tento třídicí mechanismus používá v každodenním životě.
Vezměte si například peněženku. V přihrádce na bankovky leží v nepořádku sto, pět set a tisícdolarové bankovky. To je průšvih, v takovém mišmešku je těžké hned najít ten správný papír. Pole bankovek musí být roztříděno.
Úplně první je bankovka 1000 rublů a hned po ní - 100. Vezmeme stovku a položíme ji dopředu. Třetí v řadě je 500 rublů, právoplatné místo je mezi stovkou a tisícovkou.
Stejným způsobem třídíme přijaté karty při hře „Blázna“, abychom si usnadnili orientaci v nich.
Operátory a pomocné funkce
Metoda řazení vložení bere jako vstup počáteční pole, které se má třídit, porovnávací funkci a v případě potřeby funkci, která určuje pravidlo pro výčet prvků. Nejčastěji se používá místo tohopříkaz pravidelné smyčky.
První prvek je sám o sobě uspořádanou množinou, takže srovnání začíná od druhého.
Algoritmus často používá pomocnou funkci k výměně dvou hodnot (swap). Používá další dočasnou proměnnou, která spotřebovává paměť a trochu zpomaluje kód.
Alternativou je hromadné posunutí skupiny prvků a následné vložení aktuálního prvku do volného prostoru. V tomto případě dojde k přechodu na další prvek, když porovnání poskytlo kladný výsledek, což znamená správné pořadí.
Příklady implementace
Konkrétní implementace do značné míry závisí na použitém programovacím jazyce, jeho syntaxi a strukturách.
Klasická implementace C využívající dočasnou proměnnou k výměně hodnot:
int i, j, teplota; for (i=1; i =0; j--) { if (pole[j] < temp) break; pole[j + 1]=pole[j]; pole[j]=teplota; }
Implementace PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; }
Zde jsou nejprve všechny prvky, které neodpovídají podmínce řazení, posunuty doprava a poté je aktuální prvek vložen do volného místa.
Java kód pomocí while smyčky:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } }
Obecný význam kódu zůstává nezměněn: každý prvek pole je postupně porovnáván s předchozími a v případě potřeby s nimi zaměněn.
Odhadovaná doba provozu
Je zřejmé, že v nejlepším případě bude vstupem do algoritmu pole již seřazené správným způsobem. V této situaci bude muset algoritmus jednoduše zkontrolovat každý prvek, aby se ujistil, že je na správném místě, aniž by prováděl výměny. Doba běhu tedy bude přímo záviset na délce původního pole O(n).
V nejhorším případě je vstup pole seřazené v opačném pořadí. To bude vyžadovat velký počet permutací, běhová funkce bude záviset na počtu čtverců prvků.
Přesný počet permutací pro zcela neuspořádané pole lze vypočítat pomocí vzorce:
n(n-1)/2
kde n je délka původního pole. Uspořádání 100 prvků ve správném pořadí by tedy vyžadovalo 4950 permutací.
Metoda vkládání je velmi účinná pro třídění malých nebo částečně tříděných polí. Nedoporučuje se však aplikovat ji všude kvůli vysoké složitosti výpočtů.
Algoritmus se používá jako pomocný u mnoha dalších složitějších metod třídění.
Seřadit stejné hodnoty
Algoritmus vkládání patří mezi tzv. stabilní druhy. To znamená,že nezamění shodné prvky, ale zachová jejich původní pořadí. Index stability je v mnoha případech důležitý pro správné objednání.
Výše uvedené je skvělým vizuálním příkladem řazení vkládání do tance.
