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.

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 první si musíme vybrat pivot, ten si vybereme tak, že vezeme první prvek, prostřední prvek a poslední prvek, který seřadíme a vybereme ten prostřední jako pivot.

Vybereme 3
5	2	9	3	5	1	8

Uspořádáme 3 vybranné prvky
3	2	9	5	5	1	8

Prostřední prvek jako pivot
3	2	9	5	5	1	8

Teď budeme kontrolovat pivot s prvkama z leva a zprava a zastavime se pokud najdeme potvrzeni pravidla
Zprava je menší jak pivot
Zleva je větší jak pivot

3 > 5 🚫 ↓
3	2	9	8	5	1	5
					↑ 1 < 5 ✅

	2 > 5 🚫 ↓
3	2	9	8	5	1	5
					↑ 1 < 5 ✅

		9 > 5 ✅ ↓
3	2	9	8	5	1	5
					↑ 1 < 5 ✅

Našla se shoda v obou prvkách, takže je prohodíme

3

2

1

8

5

9

5

Pokračujeme dál v kontrole

			8 > 5 ✅ ↓
3	2	1	8	5	9	5
				↑ 5 < 5 🚫

			8 > 5 ✅ ↓
3	2	1	8	5	9	5
			↑ 8 < 5 🚫

			8 > 5 ✅ ↓
3	2	1	8	5	9	5
		↑ 1 < 5 ✅

Kontrola se ukončí jakmile počítadlo z leva je větší jak zprava a prohodíme předmět z levého počítadla s pivotem. Jelikož je celá funkce rekurzivní tak se ted pole rozdělí na dvě části a to na 3, 2, 1 a 8, 5, 9. Které budou dělat uplně to samé jako původní pole.

1

2

3

5

5

8

9

        public static void QuickSort(int[] data, int start = 0, int end = -1)
        {
            if (end < 0)
                end = data.Length;

            if (start + 1 >= end)
                return;

            int boundary = start + 1;
            for (int i = boundary; i < end; i++)
            {
                if (data[i] < data[start])
                {
                    Swap(i, boundary, data);
                    boundary++;
                }
            }

            Swap(start, boundary - 1, data);
            QuickSort(data, start, boundary - 1);
            QuickSort(data, boundary, end);
        }


        public static void Swap(int a, int b, int[] data)
        {
            int tmp = data[a];
            data[a] = data[b];
            data[b] = tmp;
        }