Triedenie vkladaním

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

>Triedenie výmenou
>Triedenie vkladaním
>Triedenie zlučovaním
>Triedenie delením
>Triedenie výberom
>Triedenie - ostatné princípy

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Insert sort

Insert Sort nepatrí medzi výhodné algoritmy triedenia, nakoľko pracuje s operačnou zložitosťou O(n^2). Výsledkom jeho triedenia je stabilné pole (čiže zachová relatívne usporiadanie duplicitných kľúčov triedených prvkov). Insert Sort sa vyznačuje taktiež jednoduchou realizáciou a vhodný je hlavne na takmer usporiadané pole s malým počtom prvkov(pod 2 000). Pri usporadúvaní už usporiadaného poľa je Insert Sort dokonca rýchlejší ako Quicksort, pretože každý nový prvok porovnáva len s posledným v danom poli.

Princíp algorimtu

Princíp algoritmu Instert sort sa dá ľahko vysvetliť na princípe zotriedenia hráčskych kariet. Keď dostane hráč karty, snaží sa ich usporiadať podľa ich hodnoty jednoducho tak, že zoberie prvú kartu, ktorá netvorí žiadanú postupnosť a vloží ju na správne miesto. Samotný algoritmus, kde usporiadavame pole celých čísel od najmenšieho po najväčšie môžeme definovať ako:

1. rozdeľ triedené pole na zotriedenú a nezotriedenú časť. Na začiatku bude zotriedená časť prázdna a nezotriedená časť bude obsahovať všetky prvky. Začíname s prvkom na indexe i=0.
2. Zober prvok na indexe i z nezotriedenej časti a vlož ho na správne miesto v zotriedenej časti nasledovne:
   1. Prvok, pre ktorý hľadáme správne umiestnenie si označme x. Index posledného prvku v zotriedenej časti označme j.
   2. Porovnaj prvok x, s prvkom z zotriedenej časti (pole[j]).
   3. Ak je x < pole[j] , posuň tento prvok o jednu pozíciu doprava. Zmenši hodnotu j o 1 (posuň sa o jednu pozíciu doľava). Choď na krok 2.2
   4. Ak je x > pole[j] , tak na pozíciu j vlož prvok x.
   5. Opakuj algoritmus od začiatku (krok 2) s ďalším prvkom v nezotriedenej čast (i=i+1)

Vzorový príklad

Majme nezotriedené pole celých čísel (tabuľka 1, riadok č. 1). Jednotlivé riadky tabuľky reprezentujú iterácie triedenia. Čísla hrubo vytlačené znamenajú pozíciu prvku s ktorým v ďalšom kroku porovnávame susedný (ľavý) prvok. Červené písmo znamená aktuálnu zámenu dvoch prvkov. Zelené pozadie majú už usporiadané prvky, ktoré už nemusíme kontrolovať, či sú na správnej pozícii.

Tabuľka 1 - Insert sort

iterácia	p[0]	p[1]	p[2]	p[3]	p[4]	p[5]	operácia
1.	5	3	1	2	7	4	začiatok
2.	5	3	1	2	7	4	porovnávanie
3.	3	5	1	2	7	4	zámena 3-5. V ďalšom kroku porovnávame 1.
4.	3	1	5	2	7	4	zámena 5-1
5.	1	3	5	2	7	4	zámena 3-1
6.	1	3	2	5	7	4	zámena 5-2
7.	1	2	3	5	7	4	zámena 3-2
8.	1	2	3	5	7	4	porovnávanie 7
9.	1	2	3	5	7	4	porovnávanie 4
10.	1	2	3	5	4	7	zámena 7-4
11.	1	2	3	4	5	7	zámena 5-4
12.	1	2	3	4	5	7	koniec

Implementácia algoritmu

Insert Sort v pseudokóde

 1 insertionSort(array A)
 2 begin
 3     for i := 1 to length[A]-1 do
 4     begin
 5         value := A[i];
 6         j := i - 1;
 7         done := false;
 8         repeat
 9             if A[j] > value then
10             begin
11                 A[j + 1] := A[j];
12                 j := j - 1;
13                 if j < 0 then
14                     done := true;
15             end
16             else
17                 done := true;
18         until done;
19         A[j + 1] := value;
20     end;
21 end;

Insert Sort v C

 1 void InsertSort(int pole[ ], int pocet)
 2 {  int i,j,tmp;
 3 	for(i=1; i<pocet; i++) // cez pole prejdeme pocet krat
 4 	{	j=i; // 0..i-1 su uz zotriedene
 5 		tmp=pole[j]; // tento prvok budeme zoradovat
 6 		while( (j>0) && (pole[j-1] > tmp) ) // hladame, kde 	
 7                 {   pole[j]=pole[j-1];		// prvok vlozime
 8 		    j--;
 9 		}
10 		pole[j]=tmp;  // vlozime prvok na spravne miesto
11 	}
12 }

Shell sort

Shell sort je zovšeobecnený triediaci algoritmus insert sort. Pre insert sort platí:

• Insert sort je efektívny ak sú vstupné údaje skoro utriedené.
• Insert sort je väčšinou neefektívny, pretože presúva hodnoty len o jedny pozíciu.

Shell Sort je triediaci algoritmus, ktorý realizuje triedenie priamym vkladaním so zmenšovaním kroku. Je to vlastne zlepšenie triedenia vkladaním a bublinkového triedenia. Táto metóda je jedna z najrýchlejších pre triedenie menších postupností (1000 a menej prvkov).

Princíp algorimtu

Postupne sa porovnávajú prvky vzdialené od seba i miest - na začiatku je i=n/2, kde n je veľkosť poľa, ktoré triedime. V prípade že ľavý porovnávaný prvok je väčší ako pravý porovnávaný, tak za zamenia. Následne sa zníži i (spôsobom popísaným nižšie) a opakuje sa postup. Nakoniec je krok i=1 a prebehne obyčajné triedenie vkladaním. Triediaci algoritmus nekladie žiadne špecifické požiadavky na postupnosť dĺžok krokov.

Voľba vhodnej postupnosti skracovania kroku:

• Pri použití Shellovej postupnosti (začína na polovičnej veľkosti poľa a zakaždým sa delí 2) je to [math]O(n^2)[/math].
• Hibbardova postupnosť: [math](2^k - 1)[/math] má časovú zložitosť [math]O(n^{3/2})[/math].
• Sedgewickove postupnosti: [math]9\times4^i - 9\times2^i + 1[/math] alebo [math]4^{i} - 3\times2^i + 1[/math] majú časovú zložitosť [math]O(n^{4/3})[/math].
• Existujú aj postupnosti dosahujúce zložitosť [math]O(n.log^{2}n)[/math], ale existencia postupnosti, ktorá prináša v najhoršom prípade časovú zložitosť [math]O(n log n)[/math] zostáva otázna.

Optimálna voľba kroku je

novy_krok = round(krok * 2.2)

Vzorový príklad

Začíname s neusporiadaným poľom (tabuľka 2). Porovnávame prvok na pozícii i s prvkom na pozícii i+krok. Vysvetlivky:

d - index, pri ktorom zastavíme porovnávanie

i- aktuálny index pri porovnávaní.

žlté bunky - aktuálne porovnávané.

tučné písmo - prvky, ktoré budú v ďalšom kroku zamenené.

Tabuľka 2 - Shell sort

iterácia	p[0]	p[1]	p[2]	p[3]	p[4]	p[5]	p[6]	p[7]	operácia
1.	5	1	3	2	8	4	6	7	i=0,krok=4, d=4
2.	5	1	3	2	8	4	6	7	i=1,krok=4, d=4
3.	5	1	3	2	8	4	6	7	i=2,krok=4, d=4
4.	5	1	3	2	8	4	6	7	i=3,krok=4, d=4
5.	5	1	3	2	8	4	6	7	i=0,krok=2, d=6
6.	3	1	5	2	8	4	6	7	i=1,krok=2, d=6
7.	3	1	5	2	8	4	6	7	i=2,krok=2, d=6
8.	3	1	5	2	8	4	6	7	i=3,krok=2, d=6
9.	3	1	5	2	8	4	6	7	i=4,krok=2, d=6
10.	3	1	5	2	6	4	8	7	j=i-krok=2,krok=2, d=6
11.	5	1	3	2	6	4	8	7	i=5,krok=2, d=6
12.	5	1	3	2	6	4	8	7	i=0,krok=1, d=7
13.	1	5	3	2	6	4	8	7	i=1,krok=1, d=7
14.	1	3	5	2	6	4	8	7	i=2,krok=1, d=7
13.	1	3	2	5	6	4	8	7	j=1,krok=1, d=7
16.	1	2	3	5	6	4	8	7	j=0,krok=2, d=7
17.	1	2	3	5	6	4	8	7	i=3,krok=2, d=7
18.	1	2	3	5	6	4	8	7	i=4,krok=2, d=7
19.	1	2	3	5	4	6	8	7	j=3,krok=2, d=7
20.	1	2	3	4	5	6	8	7	j=2,krok=2, d=7
21.	1	2	3	4	5	6	8	7	i=5,krok=2, d=7
22.	1	2	3	4	5	6	8	7	i=6,krok=2, d=7
23.	1	2	3	4	5	6	7	8	j=5,krok=2, d=7

Implementácia algoritmu

Shell sort v pseudokóde

input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:
    for i = inc .. n − 1 do:
        temp ← a[i]
        j ← i
        while j ≥ inc and a[j − inc] > temp do:
            a[j] ← a[j − inc]
            j ← j − inc
        a[j] ← temp
    inc ← round(inc / 2.2)

Implementácia v jazyku C

1 void ShellSort(int A[ ],int pocet)
2 {
3  int krok = pocet;
4   while (krok /= 2) // krok pri triedeni
5     for (int d=pocet-krok, i=0; i<d; i++)
6       for (int j=i; (j>=0) && (A[j]>A[j+krok]); j-=krok ) 	
7         SWAP(A[j], A[j+m]);
8 }

Vysvetenie algorimtu:

V prípadem ak nájdeme také dva prvky (prvok A[i] a A[i+krok], ktoré treba zameniť, tak ich zameníme (riadok 7). Potom sa treba ešte presvedčiť či je nový prvok na pozícii (i-krok) väčší ako na pozícii (i). Ak áno, tak ich zameníme a posunieme sa o hodnotu kroku pozíciu vľavo (tabuľka 1, riadky 9-10, 14-16, 18-20, 22-23). Ak narazíme na takú dvojicu, že ich netreba zamieňať, tak už ďalej nemusíme porovnávať (tabuľka 2, riadky 10, 20, 23)