- Confrontate
- Evidenziate (minimo, pivot o chiave)
- Scambiate o spostate
- Al loro posto
| Posizione | Algoritmo | Confronti o letture | Scambi o spostamenti | Operazioni |
|---|
Gara di ordinamento
Qual è l'algoritmo di ordinamento più veloce? Dipende dalla lista. Gara di ordinamento esegue tutti e otto gli algoritmi di ordinamento sulla stessa lista nello stesso momento, una corsia ciascuno, e conta ogni confronto, lettura, scambio e spostamento come un'operazione. Le corsie avanzano man mano che salgono i loro conteggi, così puoi vedere gli algoritmi efficienti finire mentre quelli lenti stanno ancora scambiando, e l'ordine cambiare quando la lista è quasi ordinata o inversa. Premi Avvia per guardare gli otto algoritmi di ordinamento gareggiare sulla stessa lista, oppure Passo e Indietro per procedere un'operazione alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. Ogni confronto, lettura, scambio o spostamento conta come un'operazione, e ogni corsia avanza man mano che sale il suo conteggio, così l'algoritmo che richiede meno operazioni finisce per primo. Scegli quante barre usare e come partono, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
- Premi Avvia e guarda le otto corsie. Passo e Indietro si muovono di un'operazione alla volta; il cursore dei passi salta in qualsiasi punto della gara.
- Confronta la tabella dei risultati, poi prova una lista quasi ordinata e una inversa per vedere come cambia la classifica.
Come funziona la gara
Tutti e otto gli algoritmi ricevono la stessa lista. Ogni confronto tra due valori, ogni cifra o valore letto da radix sort e counting sort, e ogni scambio o spostamento conta come un'operazione. In ogni momento della gara, ogni corsia mostra fin dove è arrivato il suo algoritmo con quel numero di operazioni. Un algoritmo che richiede meno operazioni arriva prima in fondo. La tabella dei risultati elenca per ogni algoritmo i confronti, gli scambi o spostamenti e il totale.
Cosa mostrano i risultati
Su 40 valori casuali, il counting sort richiede circa 120 operazioni, il radix sort circa 240, il quicksort circa 260 e il merge sort circa 380. Segue l'heap sort con circa 490, mentre selection sort e insertion sort ne richiedono circa 820 e il bubble sort oltre 1.100. Su una lista quasi ordinata vince l'insertion sort con circa 50, e il bubble sort arriva secondo. Su una lista inversa, bubble sort e insertion sort ne richiedono entrambi 1.560. Counting sort e radix sort vincono così spesso perché questi valori sono piccoli numeri interi; su altri dati non si possono proprio usare.
Domande frequenti
Qual è l'algoritmo di ordinamento più veloce?
Dipende dai dati. Per piccoli numeri interi, counting sort e radix sort richiedono meno operazioni di tutti. Per dati generici, quicksort e merge sort sono i più veloci sulle liste casuali, e l'insertion sort è il più veloce sulle liste quasi ordinate. Bubble sort e selection sort sono lenti, tranne che sulle liste più piccole.
Cosa conta come operazione?
Ogni confronto tra due valori, ogni cifra o valore letto da radix sort e counting sort, e ogni scambio o spostamento di un valore. È un modello semplice: i tempi reali dipendono anche dall'accesso alla memoria e dal costo di ogni operazione.
Perché counting sort e radix sort vincono così spesso?
Perché non confrontano mai i valori. Sfruttano il fatto che i valori sono piccoli numeri interi, quindi il loro lavoro cresce con n più l'intervallo dei valori, non con n log n. Su dati che non sono piccoli interi non si applicano.
Perché l'insertion sort vince su una lista quasi ordinata?
Perché il suo lavoro è pari al numero di valori più il numero di coppie fuori ordine. Una lista quasi ordinata ha pochissime coppie di questo tipo, quindi ogni valore si sposta solo di un posto o due.
I miei numeri vengono inviati da qualche parte?
No. La gara si svolge nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor