NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Lekce 6 - Quick sort

V minulé lekci, Merge Sort, jsme si ukázali algoritmus Merge sort i se zdrojovými kódy.

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

Vizualizace

Video ukázka

Č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í kryptografii 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
  • // preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
    function divide(array &$list, $left, $right, $pivot) {
      $temp = $list[$pivot]; // prohozeni pivotu s poslednim prvkem
      $list[$pivot] = $list[$right];
      $list[$right] = $temp;
      $i = $left;
      for ($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
    }
    
    function limited_quicksort(array &$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);
      }
    }
    
    // zavola omezeny quicksort na cele pole
    function quicksort(array &$list) {
      limited_quicksort($list, 0, count($list) - 1);
    }
    
    

V další lekci, Dolní odhad složitosti problému třídění, si ukážeme dolní odhad složitosti problému třídění.


 

Předchozí článek
Merge Sort
Všechny články v sekci
Třídicí/řadicí algoritmy
Přeskočit článek
(nedoporučujeme)
Dolní odhad složitosti problému třídění
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
59 hlasů
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 se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity