Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Quick sort

Ako už názov napovedá, Quicksort je rýchly. On je dokonca najrýchlejší a je to algoritmus, ktorý sa skutočne používa v praxi k triedenie prvkov, preto bude tento článok o niečo obsiahlejšie, než ostatní. Chová sa dobre ako na malých, tak na veľkých poliach a je pamäťovo nenáročný. Algoritmus je založený na princípe rozdeľuj a panuj, ktorý sme si už vysvetlili v algoritme Merge sort.

Quicksort si označí jeden prvok v poli ako tzv. Pivot. Výberom pivotu sa zatiaľ nebudeme zaoberať a budeme ako pivot brať vždy prvý prvok v poli. Teraz zavoláme funkciu divide (rozdeľ), ktorá preusporiada pole tak, aby boli zľava prvkami menej ako pivot, potom nasledovať pivot sám a za pivotom boli prvky väčšie, než je on sám. Všimnite si, že som napísal preusporiada, nie zotriedi. Prvky sú teda medzi sebou stále rozhádzané a jediné zotriedenia spočíva v ich rozdelení pivotom. Túto operáciu sme schopní zvládnuť v lineárnom čase a tiež veľmi rýchlo. Teraz algoritmus rekurzívne zavoláme na ľavú polovicu pole pred pivotom a na pravú polovicu za pivotom (pivota už necháme tam, kde je). S tými vykonáme to isté, ako s pôvodným poľom a takto budeme pokračovať až do chvíle, kedy na vstupe dostaneme jednotkovej poľa (pole veľkosti 1). Po vynorení z rekurzie nemusíme robiť už vôbec nič, pole je zotriedené. Teraz si algoritmus predvedieme v praxi a povieme si viac o funkcii rozdeľ.

Priebeh

Pretože Quicksort je veľmi rýchly, predvedieme si ho tentoraz na poli o trochu väčším, než obvykle, aby sme z neho niečo vôbec videli :)
Máme teda pole nasledujúcich prvkov:

5 2 9 3 5 1 8
Ako pivot si vyberieme prvý prvok (5).
5 2 9 3 5 1 8
Teraz na pole zavoláme funkciu divide. Funkcia si ako prvý uloží pivot na koniec poľa, aby neprekážal a tiež aby sme sa na neho mohli ľahko odkazovať. Urobí to jednoduchým prehodením pivota s posledným prvkom.
8 2 9 3 5 1 5
Teraz si budeme držať pozíciu, od ktorej začínajú prvky väčšie, než je pivot (teda pozícia prvého väčšieho prvku, ako je pivot, ďalej už len pozície). Pretože sme na začiatku, bude mať hodnotu 0. Pole teraz prejdeme cyklom od začiatku do predposledného prvku (pretože posledný je pivot). Ak je prvok v poli menší, ako je pivot, prehodí sa s prvkom na pozíciu. Pretože v tej chvíli sa počet prvkov menších ako pivot zväčší, musíme aj pozíciu zvýšiť o 1. Až prídeme do cieľa, prehodíme samotný pivot s pozíciou (jeden z väčších prvkov sa teda dostane na koniec a pivot sám bude vymedzovať obe časti poľa). Pretože sa pozícia pivota iste posunie (ťažko bude zase na začiatku, keď sme pred neho navkládali menšie prvky), musia túto novú pozíciu funkcie divide vrátiť, aby s ním Quicksort mohol ďalej pracovať. V nasledujúcej vizualizáciu algoritmu budem pozíciu znázorňovať ako bodku.
. 8 2 9 3 5 1 5
V našom poli teda začneme prvým prvkom (8), pozíciu máme aj na začiatku. Pretože prvok 8 je určite väčšia ako pivot (5), necháme ho na mieste, s pozíciou nebudeme hýbať a pristúpime k ďalšiemu prvku (2).
. 8 2 9 3 5 1 5
2 je určite menšia ako 5, preto prvok prehodíme s prvkom na pozícii (teda prvok 2 sa prehodí s prvkom 8) a pozíciu posunieme o 1 doprava. Pristúpime k ďalšiemu prvku (9).
2 . 8 9 3 5 1 5
9 necháme na mieste (9> 5) a pristúpime k prvku 3.
2 . 8 9 3 5 1 5
3 <5, prehodíme, zvýšime pozíciu, ideme na prvok 5.
2 3 . 9 8 5 1 5
5 nie je menšia ako 5, necháme byť a ideme nie posledný prvok 1.
2 3 . 9 8 5 1 5
1 <5, prehodíme, zvýšime.
2 3 1 . 8 5 9 5
Nakoniec pivot prehodíme s prvkom na pozíciu.
2 3 1 5 5 9 8
Takto teda vyzerá pole po zavolaní funkcie divide, nesmieme zabudnúť vrátiť pozícii, aby Quicksort vedel, kde je teraz pivot. Všimnite si, že výsledok nemá sa setříděným poľom veľa spoločného, pole sa iba rozdelilo na dve časti pomocou pivotu. Takto nám v podstate vznikla 2 ďalšie pole a to [2, 3, 1] a [5, 9, 8]. Teraz sa "rozdvojíme" a pustíme Quicksort na obe vzniknutá pole (teda presnejšie na 2 časti pôvodného poľa, nové polia v podstate nevznikla, len sa na situáciu tak môžeme pozerať). Najprv spracujeme to prvá, druhá vetva bude zatiaľ chvíľu čakať. Pôvodný pole nám samozrejme nezmizne, len si budeme všímať len jeho časti a preto bude zvyšok znázornený sivo.

Vyberieme pivota (2)

2 3 1 5 5 9 8
Zavoláme na časť poľa funkciu divide, výsledok bude vyzerať takto:
1 2 3 5 5 9 8
Keď teraz pole opäť rozdelíme, dostaneme 2 jednoprvková polia a to [1] a [3]. To je presne to, čo sme chceli dosiahnuť, pretože jednoprvkové pole považujeme za triviálne zotriedené. Quicksort už na jednoprvkové pole volať funkciu divide nebude a ľavá polovica poľa je hotová. Vynoríme sa teda z rekurzie a prejdeme k pravej polovici, ktorá na nás zatiaľ čakala. Vyberieme pivota, teda prvok 5.
1 2 3 5 5 9 8
Po zavolaní funkcie divide sa iste nič nezmení, pivot zostane na začiatku a obaja prvky sú väčšie ako on. Moc si teda nepomôžeme a polia sa nám skráti len o pivot. V novej časti poľa vyberieme pivot (9).
1 2 3 5 5 9 8
Funkcia divide vráti nasledujúce výsledok:
1 2 3 5 5 8 9
Jednoprvkové pole ([8]) považujeme za zotriedené. Vynoríme sa z rekurzie a poľa je zotriedené. Na ďalšie triedenie sa môžete pozrieť na videoukážke.
1 2 3 5 5 8 9
Vizualizácia

Video ukážka

Časová zložitosť

Ohľadom stability musím dodať, že tu uvedená funkcia divide pre jednoduchosť nie je stabilný. Možno ju však napísať tak, aby stabilné bola. Ako je to však s časovou zložitosťou? Už som sa zmienil, že funkcia rozdeľ prebieha v lineárnom čase, jej časová zložitosť je teda O (n). Koľkokrát sa však vykonáva? Na to nie je jednoznačná odpoveď a ak očakávate háčik, očakávate správne. V ideálnom prípade nám funkcie divide poľa rozdelí na 2 rovnaké polovice. Keď niečo delíme na polovice, zložitosť bude iste dvojkový logaritmus, teda O (log n). A pretože samotné delenie trvá O (n), zložitosť celého algoritmu by v tomto prípade bola naša obľúbené O (n log n). Je dokázané, že Quicksort má aj v priemernom prípade naozaj túto zložitosť, aj keď polovice nie sú vždy presne dodržané.

Ako už to býva, extrémna rýchlosť Quicksort je vykúpená zlým správaním algoritmu na už predtriedených poliach. Zatiaľ čo Bubblesort si na predtriedených poliach visel na ňom, Quicksort vyberie ako pivot prvý prvok (teda najmenšie alebo najväčšie číslo) a funkcie rozdeľ potom logicky pred pivota už žiadny prvok nadá. Nové pole je teda vždy menšia len o jeden jediný prvok a druhé pole sa vôbec nevytvorí. Zložitosť nám spadne na O (n 2). S týmto problémom súvisí aj hackerské útoky na informačné systémy. Predstavte si, že viete, že nejaká firma triedi dáta v databáze pomocou Quicksort, ktorý vyberá ako pivota vždy prvý prvok. Stačí im poslať tisíce zotriedených polí, ich algoritmus sa náhle prepadne na časovú zložitosť O (n 2) a pretože server s takou záťažou nepočíta, tak spadne. Tento problém sa dá však pomerne ľahko vyriešiť, avšak je veľmi dôležité vedieť, že existuje.

Variácie Quicksort

Vyberať prvý prvok teda asi nie je úplne najlepší nápad. Keď vyberieme posledný, problém bude úplne rovnaký. Ponúka sa najjednoduchšie riešenie: vyberieme prvok prostredný alebo napríklad vždy prvok v 2/3 poľa. Útočníka síce pomäťme, ale keď bude poznať naše zdrojové kódy, dokáže opäť vyrobiť taká pole, aby zložitosť algoritmu spadla na O (n 2).

Ďalším riešením by mohlo byť vybrať vždy medián az neho urobiť pivot. Pole by sme tak delili vždy presne na 2 polovice. Dokonca aj existuje algoritmus, ktorý je schopný nájsť medián v lineárnom čase. Takýto Quicksort by mal potom zaručenou asymptoticky časovú zložitosť naozaj O (n log n). V praxi však bohužiaľ hľadanie mediánu algoritmus natoľko spomalí, že sa potom túto variantu neoplatí použiť.

Čo keby sme pivot jednoducho vyberali náhodne? Trefa, tejto verzii sa hovorí randomizovanej Quicksort. V praxi výber náhodného čísla algoritmus časovo príliš nezaťaží. Prakticky však náhodné číslo neexistuje. Čísla, ktoré generuje počítač, sa nazývajú Pseudonáhodné Číslo. Softvérové náhodné generátory totiž väčšinou pracujú so systémovým časom a číselnými radmi. Napr. unixové systémy sú známe tým, že ich generátory využívajú šum zo zvukovej karty alebo teploty procesora. Generátory používané napríklad pre armádne kryptografiu môžu využívať štiepenie izotopov a podobných javov. Ale späť k randomizovanému Quicksort - v 99% prípadov sa jedná o úplne spoľahlivý a rýchly algoritmus. Prakticky je nenapadnuteľný, aj keď teoreticky náhodné číslo neexistuje. Keby to však náhodou niekomu nestačilo, existuje ešte ďalší variant Quicksort: Introsort.

Introsort je Quicksort, ktorý nemusí byť ošetrený proti napadnutiu a môže teda vyberať ako pivot hneď prvý prvok. Navyše si však bude počítať, ako hlboké je zanorenia rekurzia. Ak presiahne log n, prepne sa Quicksort na Heapsort a zvyšok poľa je zoradený Heapsortem, ktorý má zaručenú zložitosť O (n log n) na akomkoľvek poli. Introsort sa v praxi vyskytuje veľmi často a je to teda už pravý algoritmus, ktorým väčšina programov triedi svoje dáta.

Vlastnosti algoritmu

časová zložitosť O (n log n) pre priemerný prípad, O (n 2)
stabilita Môže byť implementovaný stabilne
rýchlosť veľmi vysoká
Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť vzhľadom ku všetkým triediacim algoritmom.

Zdrojové kódy

// preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
public static int divide(int[] list, int left, int right, int pivot) {
  int temp = list[pivot]; // prohozeni pivotu s poslednim prvkem
  list[pivot] = list[right];
  list[right] = temp;
  int i = left;
  for (int j = left; j < right; j++) {
    if (list[j] < list[right]) { // prvek je mensi, nez pivot
      temp = list[i]; // prohozeni pivotu s prvkem na pozici
      list[i] = list[j];
      list[j] = temp;
      i++; // posun pozice
    }
  }
  temp = list[i]; // prohozeni pivotu zpet
  list[i] = list[right];
  list[right] = temp;
  return i; // vrati novy index pivotu
}

public static void limited_quicksort(int[] list, int left, int right) {
  if (right >= left) { // podminka rekurze
    int pivot = left; // vyber pivotu
    int new_pivot = divide(list, left, right, pivot);
    // rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1);
    limited_quicksort(list, new_pivot + 1, right);
  }
}

// zavola omezeny quicksort na cele pole
public static void quicksort(int[] list) {
  limited_quicksort(list, 0, list.length - 1);
}
// preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
public static int divide(int[] list, int left, int right, int pivot) {
  int temp = list[pivot]; // prohozeni pivotu s poslednim prvkem
  list[pivot] = list[right];
  list[right] = temp;
  int i = left;
  for (int j = left; j < right; j++) {
    if (list[j] < list[right]) { // prvek je mensi, nez pivot
      temp = list[i]; // prohozeni pivotu s prvkem na pozici
      list[i] = list[j];
      list[j] = temp;
      i++; // posun pozice
    }
  }
  temp = list[i]; // prohozeni pivotu zpet
  list[i] = list[right];
  list[right] = temp;
  return i; // vrati novy index pivotu
}

public static void limited_quicksort(int[] list, int left, int right) {
  if (right >= left) { // podminka rekurze
    int pivot = left; // vyber pivotu
    int new_pivot = divide(list, left, right, pivot);
    // rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1);
    limited_quicksort(list, new_pivot + 1, right);
  }
}

// zavola omezeny quicksort na cele pole
public static void quicksort(int[] list) {
  limited_quicksort(list, 0, list.Length - 1);
}
// preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
function divide(var list: array of integer; left, right, pivot: integer): integer;
var temp, i, j: integer;
begin
  temp:=list[pivot]; // prohozeni pivotu s poslednim prvkem
  list[pivot]:=list[right];
  list[right]:=temp;
  i:=left;
  for j:=left to right do
  if (list[j] < list[right]) then begin // prvek je mensi, nez pivot
    temp:=list[i]; // prohozeni pivotu s prvkem na pozici
    list[i]:=list[j];
    list[j]:=temp;
    inc(i); // posun pozice
  end;
  temp:=list[i]; // prohozeni pivotu zpet
  list[i]:=list[right];
  list[right]:=temp;
  result:=i; // vrati novy index pivotu
end;

// quicksort omezeny na urcitou cast pole
procedure limited_quicksort(var list: array of integer; left, right: integer);
var pivot, new_pivot: integer;
begin
  if (right >= left) then begin // podminka rekurze
    pivot:=left; // vyber pivotu
    new_pivot:=divide(list, left, right, pivot);
    // rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1);
    limited_quicksort(list, new_pivot + 1, right);
  end;
end;

// zavola omezeny quicksort na cele pole
procedure quicksort(var list: array of integer);
begin
  limited_quicksort(list, 0, length(list) - 1);
end;
# preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
def divide(list, left, right, pivot)
  temp = list[pivot] # prohozeni pivotu s poslednim prvkem
  list[pivot] = list[right]
  list[right] = temp
  i = left
  left.upto(right) do |j|
    if (list[j] < list[right]) # prvek je mensi, nez pivot
      temp = list[i] # prohozeni pivotu s prvkem na pozici
      list[i] = list[j]
      list[j] = temp
      i += 1 # posun pozice
    end
  end
  temp = list[i] # prohozeni pivotu zpet
  list[i] = list[right]
  list[right] = temp
  return i # vrati novy index pivotu
end

# quicksort omezeny na urcitou cast pole
def limited_quicksort(list, left, right)
  if (right >= left) # podminka rekurze
    pivot = left # vyber pivotu
    new_pivot = divide(list, left, right, pivot)
    # rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1)
    limited_quicksort(list, new_pivot + 1, right)
  end
end

# zavola omezeny quicksort na cele pole
def quicksort(list)
  limited_quicksort(list, 0, list.length - 1)
end

 

Všetky články v sekcii
Triediace / radiacej algoritmy
Článok pre vás napísal David Hartinger
Avatar
Užívateľské hodnotenie:
Ešte nikto nehodnotil, buď prvý!
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.
Aktivity