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

Bubble sort

Bublinkovému triedeniu sa pripisuje jednoduchosť zápisu algoritmu. Algoritmus dostal názov vďaka tomu, že menšie prvky sa „prebublinkujú“ na začiatok zoznamu.

Princíp algorimtu

Algoritmus Bubblesort je založený na porovnávaní dvoch susedných prvkov. Porovnávať môžeme dvoma spôsobmi:

1. Porovnávame zľava doprava. Ak je číslo v pravo menšie, prehodíme ho. Takto pokračujeme až na koniec poľa. V ďalšom kroku máme najväčšie číslo na konci, je na svojej pozícií. Pokračujeme ďalším krokom, kde znova prechádzame poľa okrem posledného.
2. Porovnávame sprava doľava. Ak je číslo v vľavo väčšie, prehodíme ho. Takto pokračujeme až na začiatok poľa. V ďalšom kroku máme najmenšie číslo na začiatku, teda je na svojej pozícií. Pokračujeme ďalším krokom, kde znova prechádzame pole okrem prvého prvku.

Negatíva tohto algoritmu sú napríklad:

1. často sa vyskytujú aj kroky naprázdno (neprebiehajú žiadne výmeny, pretože prvky sú už utriedené)
2. algoritmus bublinkového triedenia reaguje na vstupné dáta. Napríklad pre tieto dve vstupné polia
   • 1 4 2 6 18 20 39 40 - tento vstup požaduje iba jednu zmenu (číslo 2)
   • 4 6 18 20 39 40 2 - tento vstup vyžaduje až 6 zmien

je počet porovnaní je vždy rovnaký.

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 porovnávame susedný prvok. Žlté pozadie indikuje zámenu susedných prvkov. Zelené pozadie majú už udporiadané 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	začiatok.
2.	5	3	1	2	4	7	zámena
3.	5	3	1	2	4	7	porovnanie
4.	5	3	1	2	4	7	porovnanie
5.	5	1	3	2	4	7	zámena
6.	1	5	3	2	4	7	zámena
7.	1	5	3	2	4	7	začíname opäť z konca poľa, porovnanie
8.	1	5	3	2	4	7	porovnanie
9.	1	5	3	2	4	7	porovnanie
10.	1	5	2	3	4	7	zámena
11.	1	2	5	3	4	7	zámena
12.	1	2	5	3	4	7	začíname opäť z konca poľa, porovnanie
13.	1	2	5	3	4	7	porovnanie
14.	1	2	5	3	4	7	porovnanie
15.	1	2	3	5	4	7	zámena
16.	1	2	3	5	4	7	začíname opäť z konca poľa, porovnanie
17.	1	2	3	5	4	7	porovnanie
18.	1	2	3	4	5	7	zámena
19.	1	2	3	4	5	7	začíname opäť z konca poľa, porovnanie
20.	1	2	3	4	5	7	porovnanie
21.	1	2	3	4	5	7	začíname opäť z konca poľa, porovnanie
22.	1	2	3	4	5	7	koniec. Pole je utriedené.

Implementácia algoritmu

Zdrojové kódy funkcií pochádzajú z , .

Bubble sort v pseudokóde

Pre i od 1 po (počet prvkov - 1)
  Pre j od 1 po (počet prvkov - i)
    Ak zoznam[j] > zoznam[j+1]
      Vymeň zoznam[j] <-> zoznam[j+1]

Bubble sort v jazyku C

void BubbleSort(int *data, int pocet)
{  int i,j;
	for(i=1; i<pocet; i++)	// fazy triedenia
		for(j=pocet-1; j>=i; j--)  // prebublavanie
		   if(data[j]<data[j-1])
			SWAP(data[j],data[j-1]);
}

Bubble sort v Pythone

def bubble_sort(el):
    while True:
        for i in range(len(el)-1):
            if el[i+1] < el[i]:
                el[i], el[i+1] = el[i+1], el[i]
                break
        else: # not swapped
            break
    return el

Gnome sort

Jednoduchší princíp triedenie ako je Bubble sort je algoritmus trpasličieho triedenia (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ú iterá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;
		}
	}
}

Shake (coctail) sort

Tabuľka 3 - Shake 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	4	7	zámena, smer vľavo
3.	5	3	1	2	4	7	porovnanie, smer vľavo
4.	5	3	1	2	4	7	porovnanie, smer vľavo
5.	5	1	3	2	4	7	zámena, smer vľavo
6.	1	5	3	2	4	7	zámena, smer vľavo
7.	1	5	3	2	4	7	porovnanie, smer vpravo
8.	1	3	5	2	4	7	zámena, smer vpravo
9.	1	3	2	5	4	7	zámena, smer vpravo
10.	1	3	2	4	5	7	zámena, smer vpravo
11.	1	3	2	4	5	7	porovnanie, smer vpravo
12.	1	3	2	4	5	7	porovnanie, smer vľavo
13.	1	3	2	4	5	7	porovnanie, smer vľavo
14.	1	3	2	4	5	7	porovnanie, smer vľavo
15.	1	2	3	4	5	7	zámena, smer vľavo
16.	1	2	3	4	5	7	porovnanie, smer vpravo
17.	1	2	3	4	5	7	porovnanie, smer vpravo
18.	1	2	3	4	5	7	porovnanie, smer vpravo
19.	1	2	3	4	5	7	porovnanie, smer vľavo
20.	1	2	3	4	5	7	porovnanie, smer vľavo
21.	1	2	3	4	5	7	koniec