Triedenie výmenou

Z Kiwiki
Verzia z 22:17, 16. august 2010, ktorú vytvoril Juraj (diskusia | príspevky)
(rozdiel) ← Staršia verzia | Aktuálna úprava (rozdiel) | Novšia verzia → (rozdiel)
Skočit na navigaci Skočit na vyhledávání
Imbox draft.png
 Toto je projekt, na ktorom sa ešte stále pracuje!!

Aj keď sú v tomto dokumente použiteľné informácie, ešte nie je dokončený. Svoje návrhy môžete vyjadriť v diskusii o tejto stránke.

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ž 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 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 [1], [2].

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[3] 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[4]

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

Cocktail sort[5] 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.

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

Implementácia algoritmu

Shake sort v pseudokóde[6]

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

Shake sort v jazyku 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); 
}

Odkazy

  1. ↑ Code codex - http://www.codecodex.com/wiki/Bubble_sort
  2. ↑ sk:wiki http://sk.wikipedia.org/wiki/Bubble_sort
  3. ↑ Gnome sort - http://www.cs.vu.nl/~dick/gnomesort.html
  4. ↑ Gnome sort (wiki) http://en.wikipedia.org/wiki/Gnome_sort
  5. ↑ Coctail sort - http://www.nextdawn.nl/cocktail-sort-algorithm-or-shaker-sort-algorithm
  6. ↑ wiki:Coctail sort - http://en.wikipedia.org/wiki/Cocktail_sort
Zdroj: „http://www.kiwiki.info/index.php?title=Triedenie_výmenou&oldid=6649“