Quicksort
Quicksort è un esperimento interattivo di Algoritmi in azione, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
Il quicksort sceglie un pivot — qui l’ultimo elemento dell’intervallo (partizione di Lomuto) — e riordina l’intervallo in modo che i più piccoli vadano a sinistra e gli altri a destra. Il pivot finisce così nella sua posizione definitiva e le due parti si ordinano allo stesso modo. In media è O(n log n), ma se il pivot divide male (ad esempio con un array già ordinato o invertito) scende a O(n²).
Prova questo: Confronta un input casuale con uno invertito. Nell’array invertito il pivot è sempre il più grande o il più piccolo: guarda come salgono i confronti.
Domande frequenti
Che cosa mostra l’esperimento «Quicksort»?
Il quicksort sceglie un pivot — qui l’ultimo elemento dell’intervallo (partizione di Lomuto) — e riordina l’intervallo in modo che i più piccoli vadano a sinistra e gli altri a destra. Il pivot finisce così nella sua posizione definitiva e le due parti si ordinano allo stesso modo. In media è O(n log n), ma se il pivot divide male (ad esempio con un array già ordinato o invertito) scende a O(n²).
Come provo «Quicksort»?
Confronta un input casuale con uno invertito. Nell’array invertito il pivot è sempre il più grande o il più piccolo: guarda come salgono i confronti.
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.