Juraj na 20:17, 16. august 2010

2010-08-16T20:17:24Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} TOC ==Quick sort== Quicksort alebo tri…“

2010-03-08T21:18:39Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} __TOC__ ==Quick sort== Quicksort alebo tri…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}
__TOC__

==Quick sort==
Quicksort alebo triedenie delením je jeden z najrýchlejších známych triediacich algoritmov, založených na porovnávaní prvkov. Jeho priemerná doba výpočtu je O(n.log n) a je najlepšia zo všetkých podobných algoritmov. Jeho naprogramovanie je aj celkom jednoduché. Nevýhodou je, že pri nevhodnom usporiadaní vstupných dát môže byť časová a pamäťová náročnosť tohto algoritmu až <math>O(n^2)</math>.

===Princíp algorimtu===
Základnou myšlienkou quicksortu je rozdelenie triedenej postupnosti čísel na dve približne rovnaké časti. V jednej časti sú čísla väčšie a v druhej menšie ako istá zvolená hodnota, ktorá sa nazýva pivot. Ak je táto hodnota zvolená dobre, sú obe časti približne rovnako veľké. Ak budú obe časti samostatne roztriedené, je roztriedené i celé pole. Obe časti sa potom rekurzívne triedia rovnakým spôsobom.

[[Súbor:quicksort1.png]]

Najväčším problémom celého algoritmu je voľba pivotu. Ak sa podarí zvoliť číslo blízke mediánu triedenej časti poľa, je algoritmus najrýchlejší. Ak nie, je jeho pamäťová a časová náročnosť vyššia, ako pri všetkých ostatných algoritmov.

===Vlastnosti algoritmu===
Čas behu algoritmu je v priemernom prípade O(n log n). Dobrá časová zložitosť algoritmu spočíva v správnom výbere pivota. V ideálnom prípade je to medián (alebo hodnota blízka mediánu).Ak však je pivot zakaždým minimum alebo maximum daného podpoľa, časová zložitosť narastá na O(n2).
Preto je vhodné použiť na výber pivota jednu z nasledujúcich techník:
# Náhodný prvok – často používaná metóda. Ak ide o naozaj náhodný výber, čas triedenia je O(n log n).
# Metóda mediánu z troch čísel (prípadne z ľubovolného konštantného počtu) – vyberú sa z množiny tri prvky, z ktorých sa nájde medián a ten sa zvolí za pivota.

Qucksort nie je stabilné triedenie.

===Vzorový príklad===
Princíp algorimu Quick sort v pseudokóde
<source lang="pascal">
QuickSort (pole data, index lavy, index pravy)
begin
ak lavy<pravy
int m;
// rozdel pole vzhladom k pivotu; m – index pivota
// nalavo od P budu cisla mensie ako P
// napravo od P budu prvky vasie ako P
QuickSort(data, lavy, m-1);
QuickSort(data, m+1, pravy);

end
</source>
====Usporiadanie poľa vzhľadom na pivota====
Uvažujem pole, ktoré budeme triediť. Na začiatku aplikujeme algoritmus Quicksort na cele pole, tada od indexu (lavy) 0 po index (pravy) n-1, kde n je veľkosť triedeného poľa.
{| class=prettytable
|-
|index||''0''||''1''||''2''||''3''||''4''||''5''||''6''
|-
|hodnota||18||2||39||6||40||4||20
|}

'''1)''' Určíme pivota. Pivot bude prvok v strede. Stredný prvok vypočítame ako (index ľavého prvku + index pravého prvku)/2, kde indexy ľavý a pravý nám hovoria o intervale triedenia.

pivot=pole[(0+6)/2]=pole[3]=6

Označme pivota žltým pozadím.

'''2)''' Pole usporiadame tak, aby naľavo od pivota boli prvky menšie ako pivot a napravo od pivota prvky väčšie ako pivot. Dosiahneme to tak, že si označíme tie prvky, ktoré na danú stranu poľa nepatria. Indexom i si označíme prvý prvok v ľavej časti, ktorý tam nepatrí a indexom j si onzačíme prvý prvok (sprava) v pravej časti, ktorý tam nepatrí. Samotná implementácia je nasledovná:
# zväčšuj index i, pokiaľ platí že <math>prvok_i</math> <nowiki><</nowiki> pivot
# zmenšuj index j, pokiaľ platí že <math>prvok_j</math> <nowiki>></nowiki> pivot
Indexy i a j sa zastavia na prvkoch, ktorý nevyhovujú danej podmienke.

{| class=prettytable
|-
|18||2||39||style="background-color:yellow"|6||40||4||20
|-
|i|| || || || ||j||
|}

'''3)''' Ak platí, že i<=j, tak prvky na indexe i a j vzájomne zameníme. Index i zväčšíme o 1 a index j zmenšíme o 1.

{| class=prettytable
|-
|4||2||39||style="background-color:yellow"|6||40||18||20
|-
| ||i|| || ||j|| ||
|}

Opakujeme kroky 2) a 3), pokiaľ platí, že i<=j. Tieto kroky uvádzame v nasledujúcich tabuľkách:

Prvok 39 nepatrí na ľavú stranu. Podľa podmienky č.2 v kroku 2, index j zmenšíme ako platí <math>prvok_j</math> <nowiki><</nowiki> pivot. Index j teda zmenšíme o 1.
{| class=prettytable
|-
|4||2||39||style="background-color:yellow"|6||40||18||20
|-
| || ||i||j|| || ||
|}

Vymeníme prvky na indexoch i a j. Index i zväčšíme o 1 a index j zmenšíme o 1.

{| class=prettytable
|-
|index||''0''||''1''||''2''||''3''||''4''||''5''||''6''
|-
|hodnota||4||2||style="background-color:yellow"|6||39||40||18||20
|-
|rozdelenie|| || ||j||i|| || ||
|}

Keďže teraz platí, že i>j, ďalšie posúvanie indexov nerobíme a teraz prichádza rekurzívna časť algoritmu. Aplikujeme algoritmus Quicksort na časť pola od indexu lavy po j, a od indexu i po pravy.

{|class=prettytable
|-
|style="vertical-align:top"|
Quicksort(data,0,2)
{|class=prettytable
|-
|index||''0''||''1''||''2''
|-
|hodnota||4||style="background-color:yellow"|2||6
|}
<source lang="c">
lavy=0
pravy=2
pivot=data[(lavy+pravy)/2]=data[1]=2
</source>
Usporiadanie vzhľadom na pivota:
{|class=prettytable
|-
|index||''0''||''1''||''2''
|-
|hodnota||4||style="background-color:yellow"|2||6
|-
|rozdelenie|| ||i||j
|}
Výmena prvkov na indexoch i a j:
{|class=prettytable
|-
|index||''0''||''1''||''2''
|-
|hodnota||style="background-color:yellow"|2||4||6
|-
|rozdelenie|| ||j||i
|}
Rekurzívne volanie funkcie Quicksort:
Quicksort(data,0,1) // (lavy, j)
Quicksort(data,2,2) // (i, pravy)
|
Quicksort(data,3,6)
{|class=prettytable
|-
|index||''3''||''4''||''5''||''6''
|-
|hodnota||39||style="background-color:yellow"|40||18||20
|}
<source lang="c">
lavy=3
pravy=6
pivot=data[(lavy+pravy)/2]=data[4]=40
</source>
Usporiadanie vzhľadom na pivota:
{|class=prettytable
|-
|index||''3''||''4''||''5''||''6''
|-
|hodnota||39||style="background-color:yellow"|40||18||20
|-
|rozdelenie|| ||i|| ||j
|}
Výmena prvkov na indexoch i a j:
{|class=prettytable
|-
|index||''3''||''4''||''5''||''6''
|-
|hodnota||39||20||18||style="background-color:yellow"|40
|-
|rozdelenie|| || || i, j||
|}
Opäť posúvame indexy i a j podľa zadefinovaných pravidiel. Po tomto posúvaní budú hodnoty i a j nasledovné:
{|class=prettytable
|-
|index||''3''||''4''||''5''||''6''
|-
|hodnota||39||20||18||style="background-color:yellow"|40
|-
|rozdelenie|| || || j||i
|}
Prvky na indexe i a j už nezameníme, pretože podmienka v kroku 3 (i<=j) nie je splnená.

Rekurzívne volanie funkcie Quicksort:
Quicksort(data,3,5) // (lavy, j)
Quicksort(data,6,6) // (i, pravy)
|}
Ďalšie kroky algoritmu si jednoducho odvodíte sami.

====Implementácia v jazyku C====
<source lang="c" line>
void QuickSort(int data[ ],int lavy, int pravy)
{
if(lavy<pravy)
{
int i = lavy, j = pravy, p = data[ (lavy + pravy) / 2 ];
do {
while (data[ i ] < p) i++;
while (p < data[ j ]) j--;
if (i <= j)
{ SWAP(data[ i ], data[ j ]);
i++; j--;
}
} while (i <= j);
QuickSort(data, lavy, j);
QuickSort(data, i, pravy);
}
}
</source>

@@ Riadok 1: / Riadok 1: @@
-[[Kategória:Študijné materiály]]
+[[Kategória:Algoritmy triedenia]]
 {{Draft}}
 {{Skripta programovanie}}

Triedenie delením - História úprav

Juraj na 20:17, 16. august 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} __TOC__ ==Quick sort== Quicksort alebo tri…“

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} TOC ==Quick sort== Quicksort alebo tri…“