Triedenie výmenou

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

Gnome sort

Jednoduchší princíp triedenie ako je Bubble sort je algoritmus trpasličieho triedenie (Gnome = trpaslík). Gnome sort je založený na triediacej technike ktorú využívali holandskí záhradní trpaslíci :-) (po holandsky: tuinkabouter). Táto technika napodobuje ako triedi trpaslík radu črepníkov s kvetmi podľa veľkosti kvetov.

Princíp algoritmu

Princíp je jednoduchý: Trpaslík porovná veľkosť kvetu v črepníku pred sebou a za sebou. Ak sú v správnom poradí, tak postúpi k ďalšiemu črepníku. V opačnom prípade ich zamení a vráti sa k predchádzajúcemu črepníku.

Hraničné podmienky algoritmu: Ak už neexistuje črepník pri ktorý by sa vrátil, ide k nasledujúcemu. Ak neexistuje nasledujúci črepník (všetky sú za ním) tak trpaslík skončil triedenie.

Vzorový príklad

Majme nezotriedené pole celých čísel (tabuľka 2, riadok č. 1). Jednotlivé riadky tabuľky reprezentujú interácie triedenia. Čísla hrubo vytlačené znamenajú pozíciu trpaslíka. Žlté pozadie indikuje zámenu susedných prvkov.

Tabuľka 2 - Gnome 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	posun dopredu
3.	3	5	1	2	7	4	zamena, posun dozadu
4.	3	5	1	2	7	4	posun dopredu
5.	3	5	1	2	7	4	posun dopredu
6.	3	1	5	2	7	4	vymena, posun dozadu
7.	1	3	5	2	7	4	posun dozadu
8.	1	3	5	2	7	4	posun dopredu
9.	1	3	5	2	7	4	posun dopredu
10.	1	3	5	2	7	4	posun dopredu
11.	1	3	2	5	7	4	zamena, posun dozadu
12.	1	2	3	5	7	4	zamena, posun dozadu
13.	1	2	3	5	7	4	posun dopredu
14.	1	2	3	5	7	4	posun dopredu
15.	1	2	3	5	7	4	posun dopredu
16.	1	2	3	5	7	4	posun dopredu
17.	1	2	3	5	4	7	zamena, posun dozadu
18.	1	2	3	4	5	7	zamena, posun dozadu
19.	1	2	3	4	5	7	posun dopredu
20.	1	2	3	4	5	7	posun dopredu. Koniec

Implementácia algoritmu

Gnome sort v pseudokóde

procedure gnomeSort(a[])
    pos := 0
    while pos < length(a)
        if (pos == 0) or (a[pos] >= a[pos-1])
            pos := pos + 1
        else
            swap a[pos] and a[pos-1]
            pos := pos - 1
        end if
    end while
end procedure

Gnome sort v jazyku C

void gnomesort(int n, int ar[]) {
	int i = 0;	
	while (i < n)
	{
		if (i == 0 || ar[i-1] <= ar[i]) 
		   i++;
		else 
		{  int tmp = ar[i];
		   ar[i] = ar[i-1];
		   ar[--i] = tmp;
		}
	}
}