Algoritmi di ordinamento a confronto
Non esiste un unico algoritmo di ordinamento più veloce. Alcuni sono semplici ma lenti, altri sono veloci sui dati casuali ma inciampano su quelli ordinati, e alcuni non ordinano affatto per confronto. Far gareggiare tutti e otto sulla stessa lista mostra le differenze a colpo d'occhio.
Tre famiglie
Bubble sort, selection sort e insertion sort sono gli ordinamenti semplici. Confrontano e scambiano valori vicini e richiedono un tempo proporzionale a n² su una lista casuale. Merge sort, quicksort e heap sort dividono il lavoro in modo furbo e richiedono un tempo proporzionale a n log n, il meglio che un ordinamento possa fare quando può solo chiedere quale di due valori è più grande. Radix sort e counting sort saltano del tutto questa domanda: usano le cifre o i valori stessi, il che funziona solo con chiavi come i piccoli numeri interi.
Misurare il lavoro
La Gara di ordinamento conta un'operazione per ogni confronto, ogni cifra o valore letto e ogni scambio o spostamento. Su 40 valori casuali si arriva a circa 120 per il counting sort, 240 per il radix sort, 260 per il quicksort, 380 per il merge sort, 490 per l'heap sort, circa 820 ciascuno per selection sort e insertion sort, e oltre 1.100 per il bubble sort. I computer reali badano anche alla memoria: in pratica il quicksort è di solito più veloce di quanto suggerisca il suo conteggio, e l'heap sort più lento, per il modo in cui si muovono nella lista.
L'input conta
Su una lista quasi ordinata, l'insertion sort richiede solo circa 50 operazioni per 40 valori e il bubble sort circa 90, perché ogni valore è vicino al suo posto. Su una lista inversa gli stessi due ne richiedono 1.560, il loro caso peggiore. A selection sort, heap sort, merge sort, radix sort e counting sort l'ordine importa poco. Il quicksort con la mediana di tre gestisce bene le liste ordinate e inverse, ma con un pivot ingenuo una lista ordinata è il suo caso peggiore. Pochi valori distinti rallentano il quicksort, perché i valori uguali finiscono tutti da una parte.
Memoria e stabilità
Bubble sort, selection sort, insertion sort, quicksort e heap sort lavorano in place, con poca o nessuna memoria in più. Merge sort, radix sort e counting sort richiedono un buffer lungo quanto la lista. Un ordinamento stabile mantiene i valori uguali nel loro ordine originale: bubble sort, insertion sort, merge sort, radix sort e counting sort sono stabili, mentre selection sort, quicksort e heap sort no. La stabilità conta quando ordini dei record per un campo dopo l'altro.
Quale usare
In pratica usi l'ordinamento integrato nel tuo linguaggio di programmazione: di solito Timsort, un merge sort che usa l'insertion sort per i pezzi corti ed è veloce sui dati in parte ordinati, oppure introsort, un quicksort che ripiega sull'heap sort e usa l'insertion sort per le parti piccole. Con molte piccole chiavi intere, counting sort o radix sort possono batterli entrambi. Bubble sort e selection sort servono soprattutto per imparare.
Provalo
Apri la Gara di ordinamento e premi Avvia. Ogni corsia è un algoritmo sulla stessa lista; il numero a destra conta le sue operazioni, e una corsia diventa verde quando ha finito. Prova una lista quasi ordinata, una inversa e pochi valori distinti, e guarda cambiare l'ordine d'arrivo. Ogni algoritmo ha anche una sua app, dove puoi seguirlo passo per passo.
Domande frequenti
Qual è l'algoritmo di ordinamento più veloce?
Per dati generici, quicksort e merge sort (e gli ibridi basati su di essi, come introsort e Timsort) sono i più veloci in media, con n log n. Per piccole chiavi intere, counting sort e radix sort sono ancora più veloci. Per liste corte o quasi ordinate vince l'insertion sort.
Perché nessun ordinamento per confronto può battere n log n?
Una lista di n valori può trovarsi in n! ordini, e ogni confronto ha due esiti, quindi servono almeno log₂(n!) confronti per distinguerli tutti nel caso peggiore. Sono circa n log₂ n. Radix sort e counting sort evitano questo limite perché non confrontano.
Quali algoritmi di ordinamento sono stabili?
Bubble sort, insertion sort, merge sort, radix sort e counting sort sono stabili nelle loro forme abituali. Selection sort, quicksort e heap sort no, perché spostano i valori su lunghe distanze.
Quali ordinamenti richiedono memoria in più?
Merge sort, radix sort e counting sort richiedono un buffer lungo circa quanto la lista. Bubble sort, selection sort, insertion sort e heap sort non ne richiedono quasi, e il quicksort solo un po' per la ricorsione.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Avvia la Gara di ordinamento