© 2013 All rights reserved.
2

Řadící algoritmy #2: Quick Sort

Algoritmus Quick Sort je jedním z algoritmů, využívajících metodu Rozděl a Panuj (řeší úlohy tak, že si ji rozdělí na několik menších úloh, které řeší samostatně).

Již podle názvu je možné usoudit, že metoda řazení pomocí Quick Sort je velmi rychlá. Jedná se o jeden z nejrychlejších algoritmů, které jsou v dnešní době známé, od čehož se odvíjí velmi malá časová složitost.

Na začátku řazení se volí hodnota, která se nazývá Pivot. Pivot je počáteční „stav“, ze kterého se vychází. Pivot by měl být volen tak, aby se co nejvíce přibližoval mediánu (čím blíže mediánu se volí, tím je algoritmus rychlejší).

Pomocí pivotu řadíme celou strukturu řazených dat na dvě části. Část pravou a levnou, kdy jedna z částí je větší než pivot a druhá je menší než pivot. Tento postup neustále opakujeme a neustále volíme nový a nový pivot v jednotlivých částech a ty neustále rozřazujeme na menší a větší hodnoty, dle pravidel řazení (u číselných hodnot je rozřazována na hodnoty menší a větší). Postupně nám vzniká seřazená struktura dat.

Nejsložitější z celého algoritmu je právě volba pivotu, protože jeho volba ovlivňuje rychlost celého algoritmu. Touto problematikou se zabývá spousta různých řešení a alternativ tohoto algoritmu, se kterými se můžete setkat na internetu. V praxi se používá několik základních způsobů:

  • první prvek zpracovávané skupiny souboru dat
  • poslední prvek zpracovávané skupiny souboru dat
  • prvek uprostřed zpracovávané skupiny souboru dat
  • náhodný prvek z aktuálně zpracovávané části dat
  • průměr všech hodnot v celé části souboru dat (medián)

Program v Javě by mohl vypadat například takto:

Program rekurzivně řadí jednotlivé části, které rozděluje pivotem. Pivot je v programu volen jako levý prvek v poli čísel. Samozřejmě je možné pro volbu pivotu volit jakýkoli prvek a výsledek programu bude stejný.


Stabilní: ne
Přirozený: Ano
Minimální časová složitost: O(n log n)
Průměrná časová složitost: O(n log n)
Maximální časová složitost: O(n^2)

Volba pivotu

Jak jsem napsal, nejdůležitější na celém algoritmu je zjištění, nebo výpočet, pivotu. Pivot by měl být v ideálním případě medián, v praxi to ovšem vždy neplatí, protože výpočet mediánu může být při řazení různých struktur různě náročný a celý algoritmus se jeho výpočtem může zpomalovat.

Pro použití pivotu jsem uvedl několik základních způsobů, z nichž některé se nyní pokusím srovnat, porovnáním jejich časů, pro řazení.

Pro řazení bylo použito pole celých čísel o velikosti 6000 prvků. Toto pole bylo naplněno hodnotami:

  • hodnoty od 1 do n
  • náhodné hodnoty

Pro měření byl test spuštěn 100x, a výsledné časy a hodnoty jsou průměr těchto měření

Pole hodnot od 1 do N

Pole je vygenerováno jako posloupnost hodnot, začínajícími od 1 až do N, kdy N je celková velikost pole. Jedná se tedy o již seřazené pole:

  • Pivot je první prvek: 0.026675774 [s]
  • Pivot je poslední prvek: 0.02663383 [s]
  • Pivot je medián: 0.00027262974 [s]

Výsledek u takto seřazeného pole není ničím překvapivý. Naměřené hodnoty jsou samozřejmě nejmenší, když je pivot volen jako medián, Jelikož je pole již seřazeno a Pivot je volen správně..

Pole náhodných hodnot

Pole bylo vygenerováno jako soubor náhodných celých čísel o velikosti 1 až 6000, takže hodnoty v poli jsou podobné hodnotám z prvního měření, jenom přeházené:


Pivot je první prvek 0.024201134 [s]
Pivot je poslední prvek: 0.024809308 [s]
Pivot je medián: 0.0004194304 [s]

Ve výsledku tohoto měření, kde bylo použito pole náhodných čísel, je možné opět sledovat velké zrychlení v případě, že je Pivot volen jako medián. Celé pole je postupně řazeno a je vidět, že ani výpočet mediánu, který je v případě použití celých čísel jednoduchý, celý algoritmus nezpomalí.

Pole hodnot od N do 1

Pole bylo vygenerováno podobně jako v prvním případě, jenom s opačnou posloupností hodnot


Pivot je první prvek: 0.02717909 [s]
Pivot je poslední prvek: 0.026864517 [s]
Pivot je medián: 0.00029360127 [s]

Opět je vidět, že i když algoritmus počítá pivot, je tento způsob nejrychlejší a celé řazení se tím výrazně urychlí.

Závěrem

Řazení metodou QuickSort je jedním z nejrychlejších řadících algoritmů. Jeho rychlost však spočívá právě ve správné volbě Pivotu, o čemž jsme se přesvědčili v několika jednoduchých pokusech.

Pokud je pivot volen správně, je algoritmus velmi rychlý. Bohužel v případě, že je pivot volen špatně, může se zvětšit časová náročnost: O(n^2).

Comments (2)

Měl by sis to opravit, tohle moc fungovat nebude.

Abys neřekl, že plácám bez argumentů, tak budu tak hodný a opravím ti to:

tohle:
while( InArray[ j ] < x )
j–;
nahraď tímto:
while( InArray[ j ] > x )
j–;

a to proto, že když procházíš zleva, tak musíš najít menší prvek než je pivot.

Jinak vcelku hezké stránky ;-)

Diky

Add comment

About
Hi, i am programmer from the Czech Republic. I love web development (Ruby, Ruby on Rails, PHP, Nette) and iOS development (Objective-C, Cocoa).
To cooperate, here is my phone:
+420 608 836