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 - Bubble sort

iterácia	p[0]	p[1]	p[2]	p[3]	p[4]	p[5]	operácia
1.	5	3	1	2	7	4	.
2.	5	3	1	2	7	4	.
3.	3	5	1	2	7	4	.
4.	3	1	5	2	7	4	.
5.	1	3	5	2	7	4	.
6.	1	3	2	5	7	4	.
7.	1	2	3	5	7	4	.
8.	1	2	3	5	7	4	.
9.	1	2	3	5	7	4	.
10.	1	2	3	5	4	7	.
11.	1	2	3	4	5	7	.
12.	1	2	3	4	5	7	.

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 }