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:

Vyberieme pivota (2)

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 ²⁾ 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

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