Algoritmi di ordinamento — confronto tra Bubble Sort, Merge Sort e Quick Sort

Un algoritmo di ordinamento riordina gli stessi elementi secondo un certo criterio, per esempio dal più piccolo al più grande. Se vuoi prima la risposta breve: il bubble sort è semplice ma di solito troppo lento per liste grandi, il merge sort offre prestazioni affidabili di $O(n \log n)$, e il quick sort è spesso veloce nella pratica quando le sue partizioni restano abbastanza bilanciate.

La domanda giusta non è "qual è l'ordinamento migliore?", ma "migliore in quale condizione?". Il bubble sort insegna gli scambi locali, il merge sort mostra chiaramente il divide et impera, e il quick sort fa vedere perché la velocità nel caso medio può essere elevata anche senza una garanzia sul caso peggiore.

Cosa fanno gli algoritmi di ordinamento

Data una lista come $[5, 1, 4, 2]$, l'algoritmo deve restituire gli stessi valori in ordine:

$$[1, 2, 4, 5]$$

Sembra semplice, ma algoritmi diversi arrivano a questo risultato in modi molto diversi. Le differenze principali sono:

• come spostano gli elementi
• quante comparazioni o quanti scambi tendono a usare
• quanta memoria aggiuntiva richiedono
• quanto sono sensibili a schemi di input sfavorevoli

Bubble Sort: scambi ripetuti tra vicini

Il bubble sort percorre la lista e scambia gli elementi adiacenti che sono fuori ordine. Dopo un passaggio completo, l'elemento più grande non ancora sistemato è "salito" fino alla fine.

Su $[5, 1, 4, 2]$, il primo passaggio appare così:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Poi ripete il processo sulla parte rimanente non ordinata finché non servono più scambi.

Il bubble sort è utile soprattutto per imparare. In generale, ha complessità temporale $O(n^2)$, quindi il numero di confronti cresce rapidamente quando la lista diventa più grande. Per piccoli esempi in classe va bene. Per ordinamenti seri, di solito non è la scelta giusta.

Merge Sort: dividi, ordina, poi unisci

Il merge sort usa un'idea di divide et impera. Divide la lista in parti più piccole, ordina quelle parti e poi unisce di nuovo i pezzi ordinati.

Per $[5, 1, 4, 2]$, una rappresentazione chiara è:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Ordina ciascuna metà:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Poi unisce le due metà ordinate:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Il principale punto di forza del merge sort è la prevedibilità. Il suo tempo di esecuzione è $O(n \log n)$ nell'analisi standard, non solo in media. Il costo principale è la memoria: le implementazioni comuni basate su array usano spazio aggiuntivo durante la fase di merge.

Quick Sort: partizionare attorno a un pivot

Anche il quick sort usa il divide et impera, ma in modo diverso. Sceglie un pivot, mette gli elementi più piccoli da un lato e quelli più grandi dall'altro, e poi ordina ricorsivamente i due lati.

Usando il pivot $4$ su $[5, 1, 4, 2]$, una possibile partizione è:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Ora le parti sinistra e destra sono molto più piccole, quindi l'ordinamento termina rapidamente.

Il quick sort è spesso veloce nella pratica perché molte implementazioni partizionano in place e riducono rapidamente il problema quando il pivot divide la lista in modo abbastanza equilibrato. Ma questa condizione conta. Se le scelte del pivot sono ripetutamente sfavorevoli, per esempio producendo ogni volta un lato minuscolo e uno quasi pieno, il caso peggiore diventa $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Algoritmo	Idea di base	Tempo tipico	Tempo nel caso peggiore	Memoria aggiuntiva
Bubble sort	Scambi ripetuti tra elementi adiacenti	$O(n^2)$	$O(n^2)$	Bassa
Merge sort	Dividi, ordina le metà, unisci	$O(n \log n)$	$O(n \log n)$	Maggiore nelle comuni implementazioni su array
Quick sort	Partiziona attorno a un pivot	Spesso $O(n \log n)$	$O(n^2)$	Spesso inferiore al merge sort

Se vuoi portarti a casa un'idea pratica, è questa: il bubble sort è un algoritmo didattico, il merge sort è l'opzione stabile e prevedibile, e il quick sort è spesso la scelta più veloce nella pratica quando l'implementazione gestisce bene i pivot.

Un esempio svolto sulla stessa lista

Usa la stessa lista:

$$[5, 1, 4, 2]$$

Il bubble sort continua a correggere errori locali. Non "vede" l'intera struttura, quindi può richiedere molti passaggi.

Il merge sort prima scompone il problema in pezzi più piccoli già ordinati, poi li combina. Questa struttura è il motivo per cui le sue prestazioni restano affidabili quando la lista cresce.

Il quick sort cerca di ottenere presto una buona divisione. Se la divisione è abbastanza bilanciata, il lavoro rimanente si riduce rapidamente.

Per questo gli studenti spesso ricordano meglio i numeri di complessità dopo aver visto una lista passare attraverso ciascun metodo. I numeri non sono etichette arbitrarie. Riflettono il modo in cui l'algoritmo riduce il disordine.

Errori comuni nel confrontare gli algoritmi di ordinamento

Supporre che il Quick Sort sia sempre più veloce

Il quick sort è spesso veloce nella pratica, ma non è garantito che sia il più veloce in ogni caso. Una cattiva scelta dei pivot può penalizzarlo molto.

Trattare gli algoritmi $O(n \log n)$ come se fossero identici

Merge sort e quick sort possono avere lo stesso tasso di crescita medio senza comportarsi allo stesso modo per uso della memoria, garanzie sul caso peggiore o dettagli di implementazione.

Usare il Bubble Sort perché è facile da programmare

La facilità di scrittura del codice non coincide con l'adeguatezza. Per piccole dimostrazioni il bubble sort va bene. Per input reali più grandi, di solito fa lavoro inutile.

Dimenticare il modello di input

Questi confronti di solito assumono un ordinamento basato su confronti su input generici. Se i dati hanno una struttura speciale, ordinamenti non basati su confronti come il counting sort possono cambiare completamente la scelta.

Quando si usa ciascun algoritmo di ordinamento

Il bubble sort si usa soprattutto per insegnamento, tracciamento passo passo e esempi molto piccoli in cui la chiarezza conta più delle prestazioni.

Il merge sort si usa quando è importante un comportamento costante di $O(n \log n)$ e la memoria aggiuntiva è accettabile. È anche una scelta naturale per liste concatenate e per situazioni in cui conta la stabilità dell'ordinamento, a seconda dell'implementazione.

Il quick sort si usa quando la velocità pratica è importante e l'implementazione ha una buona strategia per il pivot o protezioni di fallback. Molte strategie di ordinamento delle librerie standard usano idee del quick sort insieme a salvaguardie, invece di una versione ingenua da manuale.

Un modo rapido per ricordare la differenza

Ricordali in base al movimento:

• il bubble sort corregge i vicini
• il merge sort costruisce metà ordinate
• il quick sort divide attorno a un pivot

Questa immagine mentale è più utile che memorizzare tre nomi e tre formule.

Prova la tua versione

Prendi la lista $[7, 3, 6, 1]$ e segui un passaggio del bubble sort, un ciclo di divisione e unione del merge sort e una partizione con pivot del quick sort. Se sai spiegare perché la lista cambia in modo diverso in ciascun caso, allora il concetto è davvero chiaro.