Math
Gara di ordinamenti
Tre ordinamenti percorrono lo stesso array alla stessa velocità in CONFRONTI, e arriva primo chi ha chiesto meno. A decidere è il disordine, non la dimensione: su un ingresso già ordinato l'inserzione usa 63 confronti e il quicksort 2016.
Cosa succede
Tre corsie, un array e un budget di lavoro comune: i tre ordinamenti avanzano dello stesso numero di confronti - o di spostamenti, se cambi unità -, quindi arriva primo quello che ha avuto bisogno di meno di quell'unità, non quello disegnato più in fretta. Ogni corsia parla la stessa lingua: le due chiavi confrontate sono bordate d'oro, una chiave appena scritta lampeggia in verde, un pivot porta un segno rosso, il tratto in lavorazione è tra parentesi, gli elementi al loro posto definitivo ricevono un piedino verde, e la chiave che l'insertion sort tiene in mano galleggia sopra il vuoto in cui cadrà. Prevedi il vincitore prima del «Via», oppure fai avanzare la gara un'unità alla volta. Prova gli input: su un array ordinato l'insertion finisce quasi subito mentre il quicksort con l'ultimo elemento come pivot incontra il suo caso peggiore; l'ordine inverso è il caso peggiore dell'insertion; con chiavi ripetute il colore è la posizione nell'input, e il merge mantiene in ordine le chiavi uguali mentre il quicksort le rimescola. Ogni corsia mostra anche il tempo reale dell'esecuzione su questo computer - una terza grandezza, mai l'unità della gara.
Equazioni del modulo
Equazioni n elementi, e la gara si corre in CONFRONTI - la grandezza a cui si riferiscono le formule l'ordinamento per inserzione SPOSTA un elemento esattamente tante volte quante sono le inversioni del vettore: un'identità su OGNI permutazione, verificata su tutte le n! per n <= 8 confronti dell'inserzione = inversioni + (n − 1) − (minimi di prefisso in i >= 1); media = n(n−1)/4 + n − H_n ESATTAMENTE: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 quicksort (Lomuto, ultimo elemento come perno) media = 2(n+1)H_n − 4n ESATTAMENTE: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 ordinamento per fusione, caso peggiore = n·ceil(lg n) − 2^ceil(lg n) + 1 - una formula, non un limite: 321 a n = 64, contro ceil(lg n!) = 296, il minimo di QUALSIASI ordinamento per confronti i due coincidono per n <= 4 e poi si allontanano; l'ordinamento per fusione scrive inoltre n·lg n elementi qualunque sia l'ingresso - 384 a n = 64 64 elementi, ogni posto rimescolato: 1001 inversioni; inserzione 1057 confronti / 1001 spostamenti, fusione 307 / 384, quicksort 352 / 306 64 elementi, ingresso già ordinato: inserzione 63, fusione 192, quicksort 2016 - e 2016 è n(n−1)/2, il caso PEGGIORE del quicksort la fusione supera l'inserzione con 15 posti rimescolati su 64 (269 contro 246): la soglia è il disordine, non la dimensione - su un ingresso casuale la fusione è in vantaggio da n = 4 chiavi uguali, 64 elementi su 8 valori: coppie lasciate in ordine inverso - inserzione 0, fusione 0, quicksort 77
