Algoritmi in azione
Algoritmi in azione è una simulazione interattiva gratuita di StudyFi Lab. Funziona direttamente nel browser, senza registrazione e senza installare nulla.
Ordinare e cercare, passo dopo passo
Esperimenti
Bubble sort
Il bubble sort confronta elementi vicini e li scambia se sono nell’ordine sbagliato. Dopo ogni passata l’elemento più grande è “risalito” fino in fondo, quindi la parte non ordinata si accorcia. Se una passata non fa scambi, l’array è ordinato. Nel caso peggiore servono n(n−1)/2 confronti, cioè O(n²).
Prova questo: Scegli l’input invertito e confronta i confronti con n(n−1)/2. Poi prova un array quasi ordinato: finisce dopo poche passate.
Insertion sort
L’insertion sort funziona come ordinare le carte in mano: la parte sinistra è già ordinata e ogni nuovo elemento (key) si sposta a sinistra finché non incontra uno più piccolo. Gli elementi più grandi scorrono di un posto a destra. Su dati casuali è O(n²), ma su dati quasi ordinati quasi O(n): un array ordinato richiede solo n−1 confronti.
Prova questo: Eseguilo su un array quasi ordinato e poi su uno invertito. Quante volte più spostamenti servono a quello invertito?
Merge sort
Il merge sort divide l’array a metà, ordina ciascuna metà allo stesso modo (ricorsione) e poi fonde le due metà ordinate: prende sempre il più piccolo dei due elementi in testa. Dimezzare dà log₂ n livelli e ogni livello elabora tutti gli n elementi, quindi il tempo è sempre O(n log n). In caso di parità prende l’elemento di sinistra, perciò è stabile.
Prova questo: Prova un array invertito e poi uno quasi ordinato della stessa dimensione. I confronti cambiano appena: l’ordine dell’input conta poco.
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²).
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.
Ricerca lineare vs binaria
La ricerca lineare controlla gli elementi uno alla volta, quindi nel caso peggiore servono n passi: O(n). La ricerca binaria funziona solo su un array ordinato: guarda al centro e, a seconda del risultato, scarta un’intera metà. Dopo ogni passo resta al massimo la metà, quindi bastano al più ⌈log₂(n+1)⌉ passi: O(log n). Con 40 elementi sono 6 passi invece di 40.
Prova questo: Imposta 40 elementi e cerca l’ultimo valore. Poi scegli un numero che non è nell’array: quanti passi servono a ciascuna ricerca per accorgersene?
Gara di ordinamento
Tutti e quattro gli algoritmi ordinano lo stesso input e in ogni corsia un passo è un confronto o uno spostamento. Gli algoritmi O(n²) (bubble e insertion) crescono con la dimensione dell’array molto più in fretta di quelli O(n log n) (merge e quick). L’ordine dipende però anche dall’input: su un array quasi ordinato spesso vince l’insertion sort.
Prova questo: Avvia la gara su un array casuale di 40 elementi, poi passa a quasi ordinato. Cambia il vincitore?
Domande frequenti
Che cos’è Algoritmi in azione?
Algoritmi in azione è una simulazione interattiva gratuita di StudyFi Lab. Funziona direttamente nel browser, senza registrazione e senza installare nulla. Ordinare e cercare, passo dopo passo
Algoritmi in azione è gratuito?
Sì. Algoritmi in azione è completamente gratuito. Funziona nel browser su computer, tablet e telefono, e non serve un account.
Cosa posso esplorare in Algoritmi in azione?
Bubble sort, Insertion sort, Merge sort, Quicksort, Ricerca lineare vs binaria, Gara di ordinamento.
Che cosa mostra l’esperimento «Bubble sort»?
Il bubble sort confronta elementi vicini e li scambia se sono nell’ordine sbagliato. Dopo ogni passata l’elemento più grande è “risalito” fino in fondo, quindi la parte non ordinata si accorcia. Se una passata non fa scambi, l’array è ordinato. Nel caso peggiore servono n(n−1)/2 confronti, cioè O(n²).
Che cosa mostra l’esperimento «Insertion sort»?
L’insertion sort funziona come ordinare le carte in mano: la parte sinistra è già ordinata e ogni nuovo elemento (key) si sposta a sinistra finché non incontra uno più piccolo. Gli elementi più grandi scorrono di un posto a destra. Su dati casuali è O(n²), ma su dati quasi ordinati quasi O(n): un array ordinato richiede solo n−1 confronti.
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.