Quick sort

Algoritmy Třídění Quick sort

Jak již název napovídá, Quicksort je rychlý. On je dokonce nejrychlejší a je to algoritmus, který se skutečně používá v praxi k třídění prvků, proto bude tento článek o něco obsáhlejší, než ostatní. Chová se dobře jak na malých, tak na velkých polích a je paměťově nenáročný. Algoritmus je založen na principu rozděl a panuj, který jsme si již vysvětlili v algoritmu Merge sort.

Quicksort si označí jeden prvek v poli jako tzv. pivot. Výběrem pivotu se prozatím nebudeme zabývat a budeme jako pivot brát vždy první prvek v poli. Nyní zavoláme funkci divide (rozděl), která přeuspořádá pole tak, aby byly zleva prvky menší než pivot, poté následovat pivot sám a za pivotem byly prvky větší, než je on sám. Povšimněte si, že jsem napsal přeuspořádá, nikoli setřídí. Prvky jsou tedy mezi sebou stále rozházené a jediné setřídění spočívá v jejich rozdělení pivotem. Tuto operaci jsme schopni zvládnout v lineárním čase a také velmi rychle. Nyní algoritmus rekurzivně zavoláme na levou polovinu pole před pivotem a na pravou polovinu za pivotem (pivota už necháme tam, kde je). S těmi provedeme to samé, jako s původním polem a takto budeme pokračovat až do chvíle, kdy na vstupu dostaneme jednotkové pole (pole velikosti 1). Po vynoření z rekurze nemusíme dělat už vůbec nic, pole je setříděné. Nyní si algoritmus předvedeme v praxi a řekneme si více o funkci rozděl.

Průběh

Protože Quicksort je velmi rychlý, předvedeme si ho tentokrát na poli o trochu větším, než obvykle, abychom z něj něco vůbec viděli :)
Máme tedy pole následujících prvků:

5 2 9 3 5 1 8

Jako pivot si vybereme první prvek (5).

5 2 9 3 5 1 8

Nyní na pole zavoláme funkci divide. Funkce si jako první uloží pivot na konec pole, aby nepřekážel a také abychom se na něj mohli snadno odkazovat. Udělá to jednoduchým prohozením pivota s posledním prvkem.

8 2 9 3 5 1 5

Nyní si budeme držet pozici, od které začínají prvky větší, než je pivot (tedy pozice prvního většího prvku, než je pivot, dále už jen pozice). Protože jsme na začátku, bude mít hodnotu 0. Pole nyní projedeme cyklem od začátku do předposledního prvku (protože poslední je pivot). Pokud je prvek v poli menší, než je pivot, prohodí se s prvkem na pozici. Protože v tu chvíli se počet prvků menších než pivot zvětší, musíme i pozici zvýšit o 1. Až dojedeme do cíle, prohodíme samotný pivot s pozicí (jeden z větších prvků se tedy dostane na konec a pivot sám bude vymezovat obě části pole). Protože se pozice pivotu jistě posune (těžko bude zase na začátku, když jsme před něj navkládali menší prvky), musí tuto novou pozici funkce divide vrátit, aby s ním Quicksort mohl dále pracovat. V následující vizualizaci algoritmu budu pozici znázorňovat jako tečku.

.8 2 9 3 5 1 5

V našem poli tedy začneme prvním prvkem (8), pozici máme také na začátku. Protože prvek 8 je jistě větší než pivot (5), necháme ho na místě, s pozicí nebudeme hýbat a přistoupíme k dalšímu prvku (2).

.8 2 9 3 5 1 5

2 je jistě menší než 5, proto prvek prohodíme s prvkem na pozici (tedy prvek 2 se prohodí s prvkem 8 ) a pozici posuneme o 1 doprava. Přistoupíme k dalšímu prvku (9).

2 .8 9 3 5 1 5

9 necháme na místě (9 > 5) a přistoupíme k prvku 3.

2 .8 9 3 5 1 5

3 < 5, prohodíme, zvýšíme pozici, jdeme na prvek 5.

2 3 .9 8 5 1 5

5 není menší než 5, necháme být a jdeme ne poslední prvek 1.

2 3 .9 8 5 1 5

1 < 5, prohodíme, zvýšíme.

2 3 1 .8 5 9 5

Nakonec pivot prohodíme s prvkem na pozici.

2 3 1 5 5 9 8

Takhle tedy vypadá pole po zavolání funkce divide, nesmíme zapomenout vrátit pozici, aby Quicksort věděl, kde je nyní pivot. Všimněte si, že výsledek nemá se setříděným polem moc společného, pole se pouze rozdělilo na dvě části pomocí pivotu. Takto nám v podstatě vznikla 2 další pole a to [2, 3, 1] a [5, 9, 8]. Nyní se "rozdvojíme" a pustíme Quicksort na obě vzniklá pole (tedy přesněji na 2 části původního pole, nová pole v podstatě nevznikla, jen se na situaci tak můžeme dívat). Nejprve zpracujeme to první, druhá větev bude zatím chvíli čekat. Původní pole nám samozřejmě nezmizí, jen si budeme všímat jen jeho části a proto bude zbytek znázorněn šedě.

Vybereme pivota (2)

2 3 1 5 5 9 8

Zavoláme na část pole funkci divide, výsledek bude vypadat takto:

1 2 3 5 5 9 8

Když nyní pole opět rozdělíme, dostaneme 2 jednoprvková pole a to [1] a [3]. To je přesně to, čeho jsme chtěli dosáhnout, protože jednoprvkové pole považujeme za triviálně setříděné. Quicksort již na jednoprvkové pole volat funkci divide nebude a levá polovina pole je hotová. Vynoříme se tedy z rekurze a přejdeme k pravé polovině, která na nás zatím čekala. Vybereme pivota, tedy prvek 5.

1 2 3 5 5 9 8

Po zavolání funkce divide se jistě nic nezmění, pivot zůstane na začátku a oba prvky jsou větší než on. Moc si tedy nepomůžeme a pole se nám zkrátí jen o pivot. V nové části pole vybereme pivot (9).

1 2 3 5 5 9 8

Funkce divide vrátí následující výsledek:

1 2 3 5 5 8 9

Jednoprvkové pole ([8]) považujeme za setříděné. Vynoříme se z rekurze a pole je setříděné. Na další třídění se můžete podívat na videoukázce.

1 2 3 5 5 8 9

Video návod

Časová složitost

Ohledně stability musím dodat, že zde uvedená funkce divide pro jednoduchost není stabilní. Lze ji však napsat tak, aby stabilní byla. Jak je to však s časovou složitostí? Již jsem se zmínil, že funkce rozděl probíhá v lineárním čase, její časová složitost je tedy O(n). Kolikrát se však provádí? Na to není jednoznačná odpověď a pokud očekáváte háček, očekáváte správně. V ideálním případě nám funkce divide pole rozdělí na 2 stejné poloviny. Když něco dělíme na poloviny, složitost bude jistě dvojkový logaritmus, tedy O(log n). A protože samotné dělení trvá O(n), složitost celého algoritmu by v tomto případě byla naše oblíbené O(n log n). Je dokázáno, že Quicksort má i v průměrném případě opravdu tuto složitost, i když poloviny nejsou vždy přesně dodrženy.

Jak již to bývá, extrémní rychlost Quicksortu je vykoupena špatným chováním algoritmu na již předtříděných polích. Zatím co Bubblesort si na předtříděných polích liboval, Quicksort vybere jako pivot první prvek (tedy nejmenší nebo největší číslo) a funkce rozděl pak logicky před pivota už žádný prvek nadá. Nové pole je tedy vždy menší jen o jeden jediný prvek a druhé pole se vůbec nevytvoří. Složitost nám spadne na O(n2). S tímto problémem souvisí i hackerské útoky na informační systémy. Představte si, že víte, že nějaká firma třídí data v databázi pomocí Quicksortu, který vybírá jako pivota vždy první prvek. Stačí jim poslat tisíce setříděných polí, jejich algoritmus se náhle propadne na časovou složitost O(n2) a protože server s takovou zátěží nepočítá, tak spadne. Tento problém lze však poměrně snadno vyřešit, nicméně je velmi důležité vědět, že existuje.

Variace Quicksortu

Vybírat první prvek tedy asi není úplně nejlepší nápad. Když vybereme poslední, problém bude úplně stejný. Nabízí se nejjednodušší řešení: vybereme prvek prostřední nebo třeba vždy prvek ve 2/3 pole. Útočníka sice zmateme, ale když bude znát naše zdrojové kódy, dokáže opět vyrobit taková pole, aby složitost algoritmu spadla na O(n2).

Dalším řešením by mohlo být vybrat vždy medián a z něj udělat pivot. Pole bychom tak dělili vždy přesně na 2 poloviny. Dokonce i existuje algoritmus, který je schopný najít medián v lineárním čase. Takový Quicksort by měl potom zaručenou asymptotickou časovou složitost opravdu O(n log n). V praxi však bohužel hledání mediánu algoritmus natolik zpomalí, že se pak tuto variantu nevyplatí použít.

Co kdybychom pivot prostě vybírali náhodně? Trefa, této verzi se říká Randomizovaný Quicksort. V praxi výběr náhodného čísla algoritmus časově příliš nezatíží. Prakticky však náhodné číslo neexistuje. Čísla, která generuje počítač, se nazývají pseudonáhodná čísla. Softwarové náhodné generátory totiž většinou pracují se systémovým časem a číselnými řadami. Např. unixové systémy jsou známé tím, že jejich generátory využívají šum ze zvukové karty nebo teploty procesoru. Generátory používané například pro armádní kriptografii mohou využívat štěpení izotopů a podobných jevů. Ale zpět k randomizovanému quicksortu - v 99% případů se jedná o naprosto spolehlivý a rychlý algoritmus. Prakticky je nenapadnutelný, i když teoreticky náhodné číslo neexistuje. Kdyby to však náhodou někomu nestačilo, existuje ještě další varianta quicksortu: Introsort.

Introsort je Quicksort, který nemusí být ošetřený proti napadení a může tedy vybírat jako pivot hned první prvek. Navíc si však bude počítat, jak hluboké je zanoření rekurze. Pokud přesáhne log n, přepne se Quicksort na Heapsort a zbytek pole je setříděný Heapsortem, který má zaručenou složitost O(n log n) na jakémkoli poli. Introsort se v praxi vyskytuje velmi často a je to tedy již pravý algoritmus, kterým většina programů třídí svá data.

Vlastnosti algoritmu

Časová složitost O (n log n) pro průměrný případ, O (n2)
Stabilita Může být implementován stabilně
Rychlost Velmi vysoká

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům.

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (2 hlasů) :
4.54.54.54.54.5


 


Miniatura
Předchozí článek
Merge Sort
Miniatura
Všechny články v sekci
Třídící/řadící algoritmy

 

 

Komentáře

Avatar
Milan Gatyas
Neregistrovaný
Avatar
Milan Gatyas:

public static void SeradQuick(object[] s, IComparer c)
{
SeradQuick(s, c, 0, s.Length - 1);
}

private static void SeradQuick(object[] s, IComparer c, int start, int end)
{
if (start >= end)
return;

object median = s[(start + end)/2];
int i = start;
int j = end;

while (i < j)
{
while (c.Compare(s[i], median) < 0)
i++;
while (c.Compare(s[j], median) > 0)
j--;

if (i < j)
{
object temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
if (i == j && c.Compare(median, s[j]) < 0)
j--;
SeradQuick(s, c, start, j);
SeradQuick(s, c, j + 1, end);
}

Podobná verze :-)

 
Odpovědět 29.1.2013 22:08
Avatar
Kit
Redaktor
Avatar
Kit:

Pokud vím, na řazení databází se používají nejčastěji B-stromy, které jsou pro seřazená data velmi efektivní, pro náhodná data také O(n log n) a nemohou spadnout na O(n2).

Odpovědět 30.1.2013 10:05
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
jigfreed
Člen
Avatar
jigfreed:

Ahoj, zarazila mě věta "Když něco dělíme na poloviny, složitost bude jistě dvojkový logaritmus, tedy O(log n)." A v závorce je uveden logaritmus desítkový? Nebo si mám opět zopakovat logaritmy? :))

 
Odpovědět 2.6.2013 1:30
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na jigfreed
David Čápka:

Máš pravdu, že by tam měla být ještě dvojka, někdy to upřesním.

Odpovědět 2.6.2013 10:16
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
xxx
Člen
Avatar
xxx:

od 1:47 tomu videu nerozumiem :( preco sa neoddeli 7 a nepracujeme dalej so zvysnymi 3 prvkami?

Editováno 26.4.2014 21:00
Odpovědět 26.4.2014 20:58
kto chce hlada sposoby, kto nechce hlada dovody...
Avatar
Filistin
Člen
Avatar
Filistin:

Mockrát děkuju. Moc mi to pomohlo. Hlavně ten postup s obrázkama na začatku.

 
Odpovědět 31.5.2015 17:16
Avatar
d.novy
Člen
Avatar
d.novy:

Když to pustím na pole o velikosti 10000, tak mi to vrací chybu.

Exception in thread "main" java.lang.Stac­kOverflowError
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:78)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)

Tj. zde

int new_pivot = divide(list, left, right, pivot, debug);
// rekurzivni zavolani na obe casti pole
limited_quicksor­t(list, left, new_pivot - 1, debug);
limited_quicksor­t(list, new_pivot + 1, right, debug);

D.

 
Odpovědět 16. listopadu 13:08
Avatar
Odpovídá na d.novy
Luboš Běhounek (Satik):

Můžeš buďto zvětšit stack a nebo lepší a čistší řešení je přepsat rekurzi na cyklus.

Editováno 16. listopadu 14:50
Odpovědět  +1 16. listopadu 14:50
:)
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 8 zpráv z 8.