Zobrazenie zdroja stránky Triedenie výmenou

[[Kategória:Algoritmy triedenia]]
{{Draft}}
{{Skripta programovanie}}
__TOC__


==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:
#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.
#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:
#často sa vyskytujú aj kroky naprázdno (neprebiehajú žiadne výmeny, pretože prvky sú už utriedené)
#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ž usporiadané prvky, ktoré už nemusíme kontrolovať, či sú na správnej pozícii.

{| border="1" cellpadding="3" cellspacing="0" class=wikitable
|+ 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||style="background-color:yellow"|'''4'''||style="background-color:yellow"|7||zámena
|-
|3.||5||3||1||'''2'''||4||7||porovnanie
|-
|4.||5||3||'''1'''||2||4||7||porovnanie
|-
|5.||5||style="background-color:yellow"|'''1'''||style="background-color:yellow"|3||2||4||7||zámena
|-
|6.||style="background-color:yellow"|'''1'''||style="background-color:yellow"|5||3||2||4||7||zámena
|-
|7.||style="background-color:lightgreen"|1||5||3||2||4||'''7'''||začíname opäť z konca poľa, porovnanie
|-
|8.||style="background-color:lightgreen"|1||5||3||2||'''4'''||7||porovnanie
|-
|9.||style="background-color:lightgreen"|1||5||3||'''2'''||4||7||porovnanie
|-
|10.||style="background-color:lightgreen"|1||5||style="background-color:yellow"|'''2'''||style="background-color:yellow"|3||4||7||zámena
|-
|11.||style="background-color:lightgreen"|1||style="background-color:yellow"|'''2'''||style="background-color:yellow"|5||3||4||7||zámena
|-
|12.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||5||3||4||'''7'''||začíname opäť z konca poľa, porovnanie
|-
|13.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||5||3||'''4'''||7||porovnanie
|-
|14.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||5||'''3'''||4||7||porovnanie
|-
|15.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:yellow"|'''3'''||style="background-color:yellow"|5||4||7||zámena
|-
|16.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||5||4||'''7'''||začíname opäť z konca poľa, porovnanie
|-
|17.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||5||'''4'''||7||porovnanie
|-
|18.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||style="background-color:yellow"|'''4'''||style="background-color:yellow"|5||7||zámena
|-
|19.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||style="background-color:lightgreen"|4||5||'''7'''||začíname opäť z konca poľa, porovnanie
|-
|20.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||style="background-color:lightgreen"|4||'''5'''||7||porovnanie
|-
|21.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||style="background-color:lightgreen"|4||style="background-color:lightgreen"|5||'''7'''||začíname opäť z konca poľa, porovnanie
|-
|22.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||style="background-color:lightgreen"|4||style="background-color:lightgreen"|5||style="background-color:lightgreen"|7||koniec. Pole je utriedené.
|}
===Implementácia algoritmu===
Zdrojové kódy funkcií pochádzajú z <ref>Code codex - http://www.codecodex.com/wiki/Bubble_sort</ref>, <ref>sk:wiki http://sk.wikipedia.org/wiki/Bubble_sort</ref>.
====Bubble sort v pseudokóde====
<source lang="delphi">
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]
</source>
====Bubble sort v jazyku C====
<source lang="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]);
}

</source>
====Bubble sort v Pythone====
<source lang="python">
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
</source>
==Gnome sort==
Jednoduchší princíp triedenie ako je Bubble sort je algoritmus trpasličieho triedenia (Gnome = trpaslík). Gnome sort<ref>Gnome sort - http://www.cs.vu.nl/~dick/gnomesort.html</ref> 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.

{| border="1" cellpadding="3" cellspacing="0" class=wikitable
|+ 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.||style="background-color:yellow"|'''3'''||style="background-color:yellow"|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||style="background-color:yellow"|'''1'''||style="background-color:yellow"|5||2||7||4||vymena, posun dozadu
|-
|7.||style="background-color:yellow"|'''1'''||style="background-color:yellow"|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||style="background-color:yellow"|'''2'''||style="background-color:yellow"|5||7||4||zamena, posun dozadu
|-
|12.||1||style="background-color:yellow"|'''2'''||style="background-color:yellow"|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||style="background-color:yellow"|'''4'''||style="background-color:yellow"|7||zamena, posun dozadu
|-
|18.||1||2||3||style="background-color:yellow"|'''4'''||style="background-color:yellow"|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<ref>Gnome sort (wiki) http://en.wikipedia.org/wiki/Gnome_sort</ref>====
<source lang="delphi">
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
</source>
====Gnome sort v jazyku C====
<source lang="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;
		}
	}
}
</source>
==Shake (coctail) sort==
Cocktail sort<ref>Coctail sort - http://www.nextdawn.nl/cocktail-sort-algorithm-or-shaker-sort-algorithm</ref> je taktiež známy ako obojsmerný Bubble sort, triedenie pretriasaním (shaker sort), triedenie vlnením (ripple sort), kyvadlové triedenie (shuttle sort) alebo tridenie so zľavou (happy hour sort). Je to varianta triedenia prebublávaním. Od Bubble sortu sa líši v tom, že samotné triedenie sa deje v oboch smeroch (Bubble sort prechádza tirdeným poľom vždy len jedným smerom).

===Princíp algorimtu===
Hlavný rozdiel medzi Bubble sortom a Shake sortom je ten, že Bubble sort prechádza triedeným poľom vždy jedným smerom. Pri každom prechode sa utriedi jeden prvok. V praxi to znamená že Bubble sort si počas behu algoritmu pamätá koľko je utriedených prvkov a prechádza len neutriedené.

Shake sort využíva princíp Bubble sortu, ale triedené pole prechádza oboma smermi. Pri prechode sprava doľava sa na ľavú pozíciu dostane najmenší prvok. Nasleduje tridenie zľava doprave, kedy sa na pravú stranu dostane najväčší prvok. Shake sort si počas behu algoritmu pamätá koľko prvok je utriedených na ľavej a koľko na pravej strane. V tejto oblasti už nemá zmysel porovnávať prvky, pretože boli utriedené v predošlých triediacich cykloch.

===Vzorový príklad===
Majme nezotriedené pole celých čísel (tabuľka 3, riadok č. 1). Čí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ž usporiadané prvky, ktoré už nemusíme kontrolovať, či sú na správnej pozícii. 
 
{| border="1" cellpadding="3" cellspacing="0" class=wikitable
|+ 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||style="background-color:yellow"|'''4'''||style="background-color:yellow"|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||style="background-color:yellow"|'''1'''||style="background-color:yellow"|3||2||4||7||zámena, smer vľavo
|-
|6.||style="background-color:yellow"|'''1'''||style="background-color:yellow"|5||3||2||4||7||zámena, smer vľavo
|-
|7.||style="background-color:lightgreen"|1||'''5'''||3||2||4||7||porovnanie, smer vpravo
|-
|8.||style="background-color:lightgreen"|1||style="background-color:yellow"|3||style="background-color:yellow"|'''5'''||2||4||7||zámena, smer vpravo
|-
|9.||style="background-color:lightgreen"|1||3||style="background-color:yellow"|2||style="background-color:yellow"|'''5'''||4||7||zámena, smer vpravo
|-
|10.||style="background-color:lightgreen"|1||3||2||style="background-color:yellow"|4||style="background-color:yellow"|'''5'''||7||zámena, smer vpravo
|-
|11.||style="background-color:lightgreen"|1||3||2||4||5||'''7'''||porovnanie, smer vpravo
|-
|12.||style="background-color:lightgreen"|1||3||2||4||'''5'''||style="background-color:lightgreen"|7||porovnanie, smer vľavo
|-
|13.||style="background-color:lightgreen"|1||3||2||'''4'''||5||style="background-color:lightgreen"|7||porovnanie, smer vľavo
|-
|14.||style="background-color:lightgreen"|1||3||'''2'''||4||5||style="background-color:lightgreen"|7||porovnanie, smer vľavo
|-
|15.||style="background-color:lightgreen"|1||style="background-color:yellow"|'''2'''||style="background-color:yellow"|3||4||5||style="background-color:lightgreen"|7||zámena, smer vľavo
|-
|16.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||'''3'''||4||5||style="background-color:lightgreen"|7||porovnanie, smer vpravo
|-
|17.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||3||'''4'''||5||style="background-color:lightgreen"|7||porovnanie, smer vpravo
|-
|18.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||3||4||'''5'''||style="background-color:lightgreen"|7||porovnanie, smer vpravo
|-
|19.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||3||'''4'''||style="background-color:lightgreen"|5||style="background-color:lightgreen"|7||porovnanie, smer vľavo 
|-
|20.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|'''3'''||4||style="background-color:lightgreen"|5||style="background-color:lightgreen"|7||porovnanie, smer vľavo
|-
|21.||style="background-color:lightgreen"|1||style="background-color:lightgreen"|2||style="background-color:lightgreen"|3||style="background-color:lightgreen"|4||style="background-color:lightgreen"|5||style="background-color:lightgreen"|7||koniec
|}
===Implementácia algoritmu===
====Shake sort v pseudokóde<ref>wiki:Coctail sort - http://en.wikipedia.org/wiki/Cocktail_sort</ref>====
<source lang="delphi">
procedure cocktailSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // ak sú prvky v nesprávnom poradí
        swap( A[ i ], A[ i + 1 ] ) // vymeň tieto 2 prvky
        swapped := true
      end if
    end for
    if swapped = false then
      // ak nenastali žiadne  výmeny, môžeme skončiť vonkajší cyklus
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // cyklus sa opakuje pokiaľ nastali nejaké výmeny
                // v opačnom prípade je zoznam utriedený 
end procedure
</source>
====Shake sort v jazyku C====
<source lang="c">
void ShakeSort(int *A, int n) 
{ int lavy = 1, pravy= n-1, I,k; 
do { 	
	for (i= pravy; i >= lavy; i--) 
	if (A[ i-1] > A[ i ])
	{	SWAP(A[ i-1 ], A[ i ]); 
		k=i;
	} 
	lavy=k+1;
	 for (i = lavy; i <= pravy; i++)
	 if (A[ i-1 ] > A[ i ]) 
	 {   	SWAP(A[ i-1 ], A[ i ]);
	     	k=i;
	 }
	pravy=k - 1;     
   } while (lavy<pravy); 
} 

</source>
=Odkazy=
<references/>