Algoritmi di ordinamento
Mettere in ordine un elenco si può fare in molti modi. Alcuni richiedono molto più lavoro di altri.
Ordinare un elenco — numeri, nomi, date — è uno dei lavori che i computer fanno più spesso. I metodi per farlo si chiamano algoritmi di ordinamento, e ne esistono parecchi. Con pochi elementi sembrano tutti uguali; con molti elementi le differenze diventano molto grandi.
Qui sotto gli algoritmi sono raggruppati in quattro famiglie, a seconda dell'idea su cui si basano. Scegliete quanti elementi ordinare e a che velocità, e guardate quanto tempo servirebbe a ciascuna famiglia.
Le parti della pagina segnate con il punto di domanda, o con una sottolineatura a puntini, hanno una breve spiegazione. Passateci sopra con il mouse per leggerla; con un clic la spiegazione resta fissa sullo schermo finché non la chiudete.
Per ogni famiglia contiamo, all'incirca, quante operazioni servono (un'operazione è un confronto fra due elementi o uno spostamento) e trascuriamo i dettagli. Per questo gli algoritmi della stessa famiglia hanno lo stesso tempo stimato, anche se nella realtà uno è un po' più rapido dell'altro. Le stime non servono a cronometrare un programma, ma a vedere come cresce il lavoro quando l'elenco si allunga.
Un computer due volte più veloce dimezza i tempi, qualunque sia la lunghezza dell'elenco. Passare dalla prima alla terza famiglia, invece, fa guadagnare tanto più quanto più l'elenco è lungo: con 40 elementi il lavoro si riduce di circa 7 volte, con un milione di elementi di circa 50.000 volte. È il motivo per cui si continuano a cercare algoritmi migliori, e non solo macchine più veloci.
Impostate “una persona, a mano” e un mazzo di 40 carte: la prima famiglia richiederebbe quasi un'ora. Chi ha provato a ordinare un mazzo sa che bastano pochi minuti. Il motivo è che nessuno esegue il Bubble Sort alla lettera, una coppia di carte alla volta: si guardano più carte insieme e si infila ciascuna al posto giusto, cioè si usa un metodo simile all'Insertion Sort, che in pratica fa meno mosse di quelle contate nella stima. Anche qui, a fare la differenza è il metodo.
Questa pagina mostra quanto lavoro richiede ogni algoritmo, ma non come si spostano gli elementi. Per vederlo esistono animazioni già pronte. Sono in inglese, ma le prime due si seguono anche senza leggere il testo.
Video
Video di pochi minuti in cui un gruppo di ballerini esegue un algoritmo: ognuno porta un numero e si sposta seguendo le regole dell'algoritmo. Li ha realizzati l'Università Sapientia, in Romania. Ci sono Bubble, Selection, Insertion, Shell, Merge, Quick e Heap Sort; i link ai singoli video sono anche nelle schede delle famiglie.
Apri il canale YouTubeConfronto
Otto algoritmi animati uno accanto all'altro, a partire da elenchi diversi: in disordine, quasi ordinati, in ordine inverso, con pochi valori diversi. Si vede che lo stesso algoritmo può essere rapido su un elenco e lento su un altro.
Apri le animazioniPasso per passo
Animazioni che si possono fermare a ogni mossa, anche su numeri scelti da voi. È l'unica delle tre risorse che mostra anche Counting Sort e Radix Sort. È più tecnica delle altre e si presta a una lezione guidata.
Apri VisuAlgo