Quick sort – rýchle triedenie pomocou pivota v Java

Triediace algoritmy sa používajú na vzostupné alebo zostupné preusporiadanie prvkov poľa alebo zoznamu podľa numerického alebo lexikografického poradia. Triedenie je veľmi dôležité pre optimálny výkon iných algoritmov, ktoré vyžadujú triedené vstupné dáta.

Existuje množstvo rozličných triediacich algoritmov. Výber vhodného algoritmu závisí na faktoroch ako veľkosť a vlastnosti vstupných dát, dostupná pamäť a požiadavky na časovú a priestorovú náročnosť.

Aby sme ti uľahčili výber, predstavíme si v našom seriáli postupne najznámejšie algoritmy triedenia dát, vysvetlíme si ich princípy, výhody a nevýhody a naprogramujeme si ich v Jave.

Dnes sa budeme venovať rýchlemu triedeniu pomocou pivota (angl. Quick sort).

Doteraz sme sa venovali nasledujúcim triediacim algoritmom:

• Triediace algoritmy: úvod do triedenia dát,
• Bubble sort – bublinkové triedenie,
• Comb sort – hrebeňové triedenie,
• Big O notácia: analýza zložitosti algoritmov,
• Selection sort – triedenie výberom,
• Insertion sort – triedenie vkladaním,
• Counting sort – triedenie počítaním,
• Heap sort – triedenie haldou,
• Merge sort – triedenie delením a spájaním.

Quick sort algoritmus

Quick sort je veľmi obľúbený, univerzálny a efektívny algoritmus triedenia dát, ktorý vytvoril v rokoch 1959 až 1961 britský počítačový vedec Tony Hoare. Podobne ako Merge sort využíva techniku “Divide and conquer”, ktorej základná myšlienka je založená na tom, že komplexný problém sa snažíme rozložiť na menšie časti a tie vyriešime samostatne.

Quick sort je zaujímavý tým, že sa snaží umiestniť na správne miesto najskôr jeden prvok poľa – nazývaný pivot, ktorý ma špeciálnu vlastnosť, že všetky prvky poľa menšie ako on sú v ľavej časti a všetky prvky poľa väčšie v pravej časti. Prvky v oboch častiach však ešte nie sú správne zotriedené, ale keďže sa pivot nachádza na správnom mieste v zotriedenom výstupnom vektore, môže poslúžiť ako miesto, kde sa dá pole rozdeliť do dvoch častí – oddielov (angl. partitions). Na obe časti sa potom nazerá ako na samostatné polia, ktorá sa dajú pomocou nových pivotov ďalej štiepiť, až pokiaľ jednotlivé časti neobsahujú iba jeden prvok. Výsledok triedenia je zozbieranie výsledkov triedenia jednotlivých partícií.

Vo všeobecnosti sa dá povedať, že Quicksort je rýchlejší ako Mergesort a Heapsort, hlavne ak máme náhodne poradie elementov vo veľkej sade dát, ktorú potrebuje zosortovať. Treba však zdôrazniť, že výkon algoritmu je výrazne závislý od vhodného výberu pivota. Nešťastný výber pivota môže viesť časovej náročnosti vyššej ako pri oboch vyššie spomenutých algoritmoch.

Quick sort – princíp fungovania algoritmu

Ako sme už vyššie spomínali, cieľom algoritmu je pre daný vstupný vektor výber takého prvku – pivota, ktorý v optimálnom prípade rozdelí vektor na dva približne veľké oddiely a všetky prvky vľavo sú menšie a vpravo väčšie ako pivot. Najhorší scenár nastane, ak vyberieme pivot, kde (takmer) všetky prvky sú vľavo od pivota, alebo vpravo. Preto existuje viacero metód ako vyberať pivota. Quick sort algoritmu pozostáva z nasledujúcich krokov:

1. výber pivot elementu,
2. preusporiadanie poľa,
3. rozdeľenie poľa do partícii.

Quick sort – výber pivot elementu

Existuje mnoho spôsobov výberu pivot elementu. Medzi najjednoduchšie patrí napr. výber prvého prvku, výber posledného prvku, výber náhodného prvku, výber stredného prvku atď. Existujú aj komplikovanejšie verzie výberu pivota, kedy si napríklad vyberieme náhodne tri prvky a ako pivot použijeme medián.

Quick sort – preusporiadanie poľa

Predpokladajme, že sme si vybrali ako pivota posledný prvok poľa. Postupne porovnávame jednotlivé prvky od začiatku až po pivota. Ak je aktuálny prvok poľa väčší ako pivot, tak ideme na ďalší prvok, ak je prvok menší, tak ho vymeníme za jeden z predchádzajúcich väčších prvkov. Pri prechádzaní budeme potrebovať dva indexy, prvý index určuje aktuálne porovnávaný prvok s pivotom, druhý index určuje, kde končia prvky menšie ako pivot. Akonáhle sa prvý index dostane až k pivotu, pivot vymeníme za prvý prvok väčší ako pivot (aktuálna pozícia druhého indexu). Prácu s týmito indexami potom lepšie pochopíme na príklade v Jave.

Quick sort – rozdelenie poľa do partícii

Pivot je po preusporiadaní poľa na správnej pozícii a považuje sa za zatriedený prvok. Zároveň nám rozdeľuje pôvodné pole do dvoch oddielov, ktoré rekurzívne spracujeme ako dve samostatné polia, ktoré treba zotriediť. Postupne sa opakujú kroky 1 až 3. Rekurzia skončí, ak nám ostatne v poli jediný element. Výsledok triedenia potom predstavujú jednotlivé elementy zo všetkých partícií.

Quick sort animácie, vizualizácia, gif

Animácia quick sort vyzerá nasledovne:

Zdroj: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

Animáciu algoritmu nájdeš napríklad na stránke Toptal. Nachádza sa tam 8 typov algoritmov, animáciu si môžeš pustiť aj pozadu.

Na tejto stránke si môžeš prejsť jednotlivými krokmi algoritmu, vďaka čomu si vieš overiť časovú náročnosť algoritmu.

Výhody algoritmu Quick sort

• Efektívny pre obrovské sady náhodných dát,
• pri triedení sa nekopírujú dáta (In-place sorting),
• dá sa paralelizovať a rozložiť tak výpočtovú záťaž na viac procesorov.

Nevýhody algoritmu Quick sort

• Nie je stabilný,
• citlivý na vhodný výber pivota,
• nevhodný pre malé sady dát kvôli réžii spojenej s rekurzívnymi volaniami a správou partícií.

Quick sort – časová náročnosť

Quick Sort – implementácia, Java kód

Teraz si ukážeme implementáciu algoritmu Quick sort v Jave.

QuickSort.java

package sorting;

public class QuickSort {
    public void sort(int[] data, int low, int high)
    {
        if (low >= high)
            return;
        // Pivot index (pi)
        int pi = partition(data, low, high);
        // Sort both parts of array recursively
        sort(data, low, pi - 1);
        sort(data, pi + 1, high);
    }
    
    private int partition(int[] data, int low, int high) {
        // Selection of pivot (last element)
        int pivot = data[high];
        // Index of last element smaller than pivot
        int i = (low - 1);
        // Compare each element with pivot
        for (int j = low; j < high; j++) {
            if (data[j] <= pivot) {
                // Swap the smaller element with greater placed on (i+1)
                int temp = data[++i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        // Swap of pivot
        int temp = data[++i];
        data[i] = data[high];
        data[high] = temp;
        // Print some algo information
        System.out.println("Pivot selected: " + data[i]);
        printArray(data, low, i - 1);
        System.out.print("(" + data[i] + ") ");
        printArray(data, i + 1, high);
        System.out.println();
        // Returns the pivot index
        return i;
    }

    // Function to print an array
    public void printArray(int[] data)
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
    }
    public void printArray(int[] data, int low, int high)
    {
        for (int i = low; i <= high; i++)
            System.out.print(data[i] + " ");
    }
}

Main.java

import sorting.QuickSort;

public class Main {
    public static void main(String[] args) {
        int[] dataToSort = { 9, 1, 8, 2, 7, 3, 5, 6, 4 };
        QuickSort quickSort = new QuickSort();
        System.out.print("Input: ");
        quickSort.printArray(dataToSort);
        System.out.println();
        quickSort.sort(dataToSort, 0, dataToSort.length - 1);
        System.out.print("Sorted: ");
        quickSort.printArray(dataToSort);
    }
}

Výstup z tohto príkladu je:

Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si kód Java QuickSort tu.

Ak si Java programátor a hľadáš prácu, pozri si naše benefity pre zamestnancov a reaguj na najnovšie ponuky práce.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.