Čo je algoritmus rýchleho triedenia [Vysvetlené na príkladoch]

Algoritmus rýchleho triedenia je triediaci algoritmus rozdeľuj a panuj, ktorý funguje tak, že rekurzívne rozdeľuje vstupné pole na menšie a menšie podpole, kým každé podpole neobsahuje iba jeden prvok. Algoritmus je rýchly, efektívny a široko používaný v informatike.

Ako funguje rýchle triedenie:

1. Rozdeliť: Vyberte pivot prvok z poľa (často posledný prvok).

2. Oddiel: Zmeňte usporiadanie poľa tak, aby všetky prvky menšie ako pivot boli naľavo od pivotu a všetky prvky väčšie ako pivot boli napravo. Otočný prvok je vo svojej konečnej zoradenej polohe.

3. Rekurz: Opakujte vyššie uvedené dva kroky pre ľavé a pravé podpole, rekurzívne ich rozdeľte, kým každé podpole nebude obsahovať iba jeden prvok.

Príklad 1:

Zvážte pole [5, 3, 8, 2, 1, 4].

a. Rozdeliť:Vyberte posledný prvok, 1 ako pivot.

b. Oddiel:

- Zmeňte usporiadanie poľa:[3, 2, 1, 5, 4, 8] (1 je na svojej zoradenej pozícii).

c. Rekurzia:

- Ľavé podpole:[3, 2, 1] (už zoradené)

- Pravé podpole:[5, 4, 8] (rekurzívne použiť rýchle triedenie)

Po aplikovaní rýchleho triedenia na obe podpolia je konečné triedené pole:[1, 2, 3, 4, 5, 8].

Príklad 2:

Triedenie väčšieho poľa

Uvažujme pole [7, 2, 9, 5, 3, 4, 1, 8, 6].

a. Rozdeliť:Vyberte posledný prvok, 6, ako pivot.

b. Oddiel:

- Zmeňte usporiadanie poľa:[2, 5, 3, 4, 1, 7, 9, 6] (6 je na zoradenej pozícii).

c. Rekurzia:

- Ľavé podpole:[2, 5, 3, 4, 1] (rekurzívne použiť rýchle triedenie)

- Pravé podpole:[7, 9] (už zoradené)

Po dokončení rekurzívnych volaní je zoradené pole:[1, 2, 3, 4, 5, 6, 7, 8, 9].

Časová zložitosť:

- Najlepší prípad:O(n log n)

- Priemerný prípad:O(n log n)

- Najhorší prípad:O(n^2) (nastane, keď je pole už zoradené alebo naopak zoradené)

Algoritmus rýchleho triedenia celkovo ponúka efektívne riešenie triedenia s dobrou časovou zložitosťou priemerného prípadu O(n log n). Jeho jednoduchosť a všestrannosť z neho urobili populárny algoritmus na triedenie úloh v rôznych programovacích jazykoch.

• Predchádzajúca strana: Čo je algoritmus zoraďovania zlúčenia [Vysvetlené na príkladoch] 
• Ďalšia strana: Čo je to algoritmus bublinového triedenia [Vysvetlené na príkladoch]