Sorting Race — scommetti sull'algoritmo più veloce
Due algoritmi di ordinamento corrono sullo stesso array. Scommetti sul vincitore: la complessità migliore perde più spesso di quanto credi. Gratis.
Sei gare. Stesso array, due algoritmi: scegli quello che secondo te finirà prima.
Come si gioca
- Due ordinamenti, un array. Punta su quello che finirà prima, poi guarda.
- Vince chi usa meno operazioni — confronti più spostamenti — non chi ha la complessità teorica migliore.
- Leggi la dimensione e la forma. Sotto la ventina di barre vincono i semplici; su un array quasi ordinato l'inserimento batte tutto.
- Una scelta giusta paga 50, una sbagliata costa 50. Sei gare, e parti con 100.
Come funziona
Due algoritmi di ordinamento corrono sullo stesso array, disegnato a barre, e tu scommetti su quale finirà prima. Ogni turno mette un ordinamento O(n log n) contro uno O(n²), quindi c'è sempre un favorito ovvio — e il favorito ovvio sbaglia più o meno una volta su due. A decidere davvero sono la dimensione dell'array e la sua forma: l'ordinamento per inserimento finisce un array quasi ordinato con un ventesimo delle operazioni che servono a un quicksort ingenuo, e sotto la ventina di elementi le costanti pesano più del comportamento asintotico — ed è esattamente per questo che le librerie di ordinamento reali passano all'inserimento a quelle dimensioni. Il vincitore è deciso dal numero di operazioni, non da un cronometro, quindi il risultato è lo stesso su qualunque macchina. Gira sul tuo dispositivo, non viene inviato nulla e non c'è niente da registrare.
Operazioni significa confronti più spostamenti di dati, con uno scambio che conta una volta, su implementazioni da manuale. Gli ordinamenti veri delle librerie sono ibridi e vincerebbero quasi ogni gara: è proprio il punto.
Domande frequenti
L'algoritmo migliore non è sempre il più veloce?
A queste dimensioni no. La notazione O descrive come cresce il costo, non quanto vale, e nasconde del tutto la costante. Misurato su 400 partite: puntare sulla complessità teorica migliore azzecca 3,19 su 6, contro 3,00 puntando sempre sullo stesso lato. Due regole — un array quasi ordinato e uno piccolo favoriscono entrambi l'ordinamento semplice — azzeccano circa 4,8 su 6.
Come si decide il vincitore?
Contando confronti e spostamenti, calcolati prima di disegnare qualsiasi cosa. L'animazione riproduce quel conteggio allo stesso ritmo su entrambi i lati, quindi chi richiede meno operazioni finisce prima sullo schermo per lo stesso motivo per cui vince. Un visualizzatore che facesse girare due cicli in tempo reale darebbe una risposta diversa su una macchina veloce e su una lenta.
Perché a volte il quicksort va così male?
Usa l'ultimo elemento come pivot, la versione ingenua. Su un array già o quasi ordinato quel pivot è la scelta peggiore possibile, le partizioni degenerano e fa lavoro quadratico proprio sull'input che l'ordinamento per inserimento risolve più in fretta. Le implementazioni reali scelgono mediana di tre o pivot casuale proprio per evitarlo.
Cosa significano le forme dell'array?
Casuale è mescolato. Quasi ordinato è in ordine a parte pochi scambi adiacenti. Invertito è esattamente al contrario. Pochi valori ne ha solo quattro distinti, ed è lì che la partizione di un quicksort ingenuo si sfascia. Dente di sega ripete più volte la stessa rampa.