Na riešenie problému triedenia poľa existuje niekoľko základných algoritmov. Jedným z najznámejších z nich je vkladanie triedenia. Pre svoju prehľadnosť a jednoduchosť, no nízku efektivitu sa táto metóda využíva najmä pri výučbe programovania. Umožňuje vám pochopiť základné mechanizmy triedenia.
Popis algoritmu
Podstatou algoritmu triedenia vloženia je, že vo vnútri počiatočného poľa sa vytvorí správne usporiadaný segment. Každý prvok sa porovnáva jeden po druhom so zaškrtnutým dielom a vkladá sa na správne miesto. Po opakovaní všetkých prvkov sa teda zoradia v správnom poradí.
Poradie výberu prvkov môže byť ľubovoľné, možno ich vybrať ľubovoľne alebo podľa nejakého algoritmu. Najčastejšie sa sekvenčné vyčíslenie používa od začiatku poľa, kde sa vytvorí usporiadaný segment.
Začiatok triedenia môže vyzerať takto:
- Vezmite prvý prvok poľa.
- Keďže to nie je s čím porovnávať, berte samotný prvok podľa objednávkysekvencia.
- Prejdite na druhú položku.
- Porovnajte ho s prvým na základe pravidla triedenia.
- V prípade potreby vymeňte prvky na miestach.
- Vezmite prvé dva prvky ako usporiadanú postupnosť.
- Prejdite na tretiu položku.
- Porovnajte ho s druhým, v prípade potreby vymeňte.
- Ak dôjde k výmene, porovnajte ju s prvou.
- Vezmite tri prvky ako usporiadanú postupnosť.
A tak ďalej až do konca pôvodného poľa.
Vloženie v reálnom živote
Pre prehľadnosť stojí za to uviesť príklad toho, ako sa tento triediaci mechanizmus používa v každodennom živote.
Vezmite si napríklad peňaženku. Sto, päťsto a tisícdolárové bankovky ležia v neporiadku v priehradke na bankovky. To je neporiadok, v takom mišušku je ťažké hneď nájsť ten správny papierik. Pole bankoviek sa musí triediť.
Úplne prvá je bankovka 1000 rubľov a hneď po nej - 100. Vezmeme stovku a položíme ju dopredu. Tretí v rade je 500 rubľov, právoplatné miesto je medzi stovkou a tisíckou.
Rovnakým spôsobom triedime prijaté karty pri hraní „blázna“, aby sme v nich uľahčili navigáciu.
Operátori a pomocné funkcie
Metóda zoradenia vloženia berie ako vstup počiatočné pole, ktoré sa má zoradiť, porovnávaciu funkciu a v prípade potreby funkciu, ktorá určuje pravidlo pre enumeráciu prvkov. Najčastejšie sa používa namiesto tohopríkaz s pravidelnou slučkou.
Prvý prvok je sám o sebe usporiadanou množinou, takže porovnanie začína od druhého.
Algoritmus často používa pomocnú funkciu na výmenu dvoch hodnôt (swap). Používa dodatočnú dočasnú premennú, ktorá zaberá pamäť a trochu spomaľuje kód.
Alternatívou je hromadný posun skupiny prvkov a následné vloženie aktuálneho prvku do voľného priestoru. V tomto prípade k prechodu na ďalší prvok dôjde, keď porovnanie poskytlo kladný výsledok, ktorý označuje správne poradie.
Príklady implementácie
Konkrétna implementácia do značnej miery závisí od použitého programovacieho jazyka, jeho syntaxe a štruktúr.
Klasická implementácia C využívajúca dočasnú premennú na výmenu hodnôt:
int i, j, teplota; for (i=1; i =0; j--) { if (pole[j] < temp) break; pole[j + 1]=pole[j]; pole[j]=teplota; }
Implementácia PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; }
Najprv sa všetky prvky, ktoré nezodpovedajú podmienke zoradenia, posunú doprava a potom sa aktuálny prvok vloží do voľného miesta.
Java kód pomocou while loop:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey --; } }
Všeobecný význam kódu zostáva nezmenený: každý prvok poľa sa postupne porovnáva s predchádzajúcimi a v prípade potreby sa s nimi vymení.
Odhadovaný čas prevádzky
Je zrejmé, že v najlepšom prípade bude vstupom algoritmu pole už usporiadané správnym spôsobom. V tejto situácii bude musieť algoritmus jednoducho skontrolovať každý prvok, aby sa ubezpečil, že je na správnom mieste bez vykonania výmen. Čas chodu bude teda priamo závisieť od dĺžky pôvodného poľa O(n).
Vstup v najhoršom prípade je pole zoradené v opačnom poradí. Bude to vyžadovať veľký počet permutácií, funkcia runtime bude závisieť od počtu štvorcových prvkov.
Presný počet permutácií pre úplne neusporiadané pole možno vypočítať pomocou vzorca:
n(n-1)/2
kde n je dĺžka pôvodného poľa. Na usporiadanie 100 prvkov v správnom poradí by teda bolo potrebných 4950 permutácií.
Metóda vkladania je veľmi efektívna na triedenie malých alebo čiastočne triedených polí. Neodporúča sa však aplikovať ho všade kvôli vysokej zložitosti výpočtov.
Algoritmus sa používa ako pomocný pri mnohých ďalších zložitejších metódach triedenia.
Zoradiť rovnaké hodnoty
Algoritmus vkladania patrí medzi takzvané stabilné druhy. To znamená,že nezamieňa identické prvky, ale zachováva ich pôvodné poradie. Index stability je v mnohých prípadoch dôležitý pre správne objednanie.
Vyššie uvedené je skvelým vizuálnym príkladom triedenia vkladania do tanca.
