Come funziona?

Quick Sort segue tre passaggi: scegliere un pivot, partizionare e ricorrere.

Procedura passo dopo passo:

1. Scegliere un pivot: scegli un elemento come pivot. In questo corso usiamo sempre l'elemento ultimo.
2. Partizionare: esamina gli altri elementi e dividili in quelli minori di pivot e quelli maggiori o uguali ad esso.
3. Ricorrere: ordina allo stesso modo il gruppo più piccolo e quello più grande, poi riuniscili come gruppo più piccolo ordinato + pivot + gruppo più grande ordinato.

Esempio con [7, 2, 9, 4]:

• Il pivot è 4 (l'ultimo elemento). Partiziona il resto [7, 2, 9]: gli elementi minori di 4 sono [2], il resto è [7, 9].
• Ordina [2] (già ordinato) e ordina [7, 9] (pivot 9, dà [7, 9]).
• Combina: [2] + [4] + [7, 9] = [2, 4, 7, 9].