Ako správne predpokládate, predchádzajúca úloha sem nebola je zaradená úplne náhodne a má s quick sortom priamy súvis. Úloha znie tak, že máme pole celých čísel $A$ a číslo $p$. Toto číslo nazývame pivot. Našou úlohou je rozdeliť pole na tri menšie polia, čísla menšie ako $p$, čísla rovnaké ako $p$ a čísla väčšie ako $p$. Naviac nás vôbec nezaujíma vzájomné poradie prvkov v týchto poliach.
Riešenie je samozrejme veľmi jednoduché. Stačí postupne prechádzať naším poľom $A$ a rozdeľovať prvky po poradí do príslušného výsledného poľa. Ako nám však toto pomôže pri triedení celého poľa $A$. No vieme, že výsledok bude vyzerať nasledovne: najskôr pôjdu zoradené prvky menšie ako $p$, potom prvky rovné $p$ a na záver zoradené prvky väčšie ako $p$. To znamená, že sme si našu úlohu rozdelili opäť na dve menšie časti, na ktoré sa potrebujeme rekurzívne zavolať.
Otázkou ostáva, že ako zvoliť pivot. Ukáže sa, že rozumná voľba je vybrať ako pivot jednoducho náhodný prvok z úseku poľa, ktorý triedime. Prečo je to tak si môžete podrobnejšie prečítať v časti o zložitosti quick sortu.
Pseudokód quicksortu teda môže vyzerať nejako takto:
def rozdel(A, pivot):
...
def quicksort(A):
# ak je pole dost male, uz je rovno utriedene
if len(A)==1:
return A
pivot = ... # nahodny prvok z pola A
mensie, rovne, vacsie = rozdel(A, pivot)
mensie = quicksort(mensie)
vacsie = quicksort(vacsie)
return mensie+rovne+vacsie