Insertion sort
L'insertion sort (ordinamento per inserimento) è il modo in cui quasi tutti ordinano le carte in mano: si prende la carta successiva e la si infila al posto giusto tra quelle già in ordine. È lento sulle liste lunghe e casuali, ma molto veloce su quelle brevi o quasi ordinate, ed è per questo che le vere librerie di ordinamento lo usano ancora.
L'idea
Tieni ordinato l'inizio della lista. All'inizio quella parte ordinata è solo il primo valore. Prendi il valore successivo e confrontalo con quello prima. Se quello è più grande, scambiali e confronta di nuovo, un posto più indietro. Fermati quando il valore prima non è più grande, o quando il valore arriva in testa. La parte ordinata è cresciuta di uno. Ripeti con ogni valore fino alla fine.
Un esempio
Prendi 5, 1, 4, 2, 8. La passata 1 prende 1: 5 è più grande, quindi si scambiano, e 1 arriva in testa: 1, 5, 4, 2, 8. La passata 2 prende 4: si scambia con 5, poi si ferma a 1: 1, 4, 5, 2, 8. La passata 3 prende 2: si scambia con 5 e con 4, poi si ferma a 1: 1, 2, 4, 5, 8. La passata 4 prende 8, che è già più grande di 5, quindi basta un confronto. In tutto 7 confronti e 4 scambi. Il bubble sort richiede 9 confronti sulla stessa lista, il selection sort 10.
Gli scambi sono pari alle inversioni
Un'inversione è una coppia di valori nell'ordine sbagliato. Scambiare due vicini fuori ordine elimina esattamente un'inversione, e l'insertion sort scambia solo vicini di questo tipo. Fa quindi esattamente tanti scambi quante sono le inversioni della lista iniziale, lo stesso numero del bubble sort. Ogni passata fa anche al massimo un confronto che non porta a uno scambio, quello che la ferma. Quindi i confronti sono le inversioni più al massimo n − 1.
Adattivo: veloce quando la lista è quasi ordinata
Poiché il lavoro è il numero di inversioni più circa n, l'insertion sort è veloce ogni volta che le inversioni sono poche. Una lista ordinata richiede n − 1 confronti e nessuno scambio. Una lista in cui ogni valore è solo a pochi posti dal suo richiede un tempo vicino a n. Solo una lista lontana dall'essere ordinata, come una inversa con n(n − 1)/2 inversioni, richiede un tempo proporzionale a n². Su una lista casuale la media è di circa n²/4 scambi.
Dove si usa
L'insertion sort è stabile, non richiede memoria aggiuntiva e ha pochissimo overhead. Sulle liste brevi batte algoritmi più veloci sulla carta. Molti ordinamenti di libreria, come Timsort in Python e Java e l'introsort usato in C++, passano all'insertion sort per i pezzi piccoli della lista, di solito fino a qualche decina di valori. È adatto anche a dati che arrivano un valore alla volta, perché ogni nuovo valore può essere inserito appena arriva.
Provalo
Apri l'app e premi Avvia, oppure premi Passo per procedere un confronto alla volta. Il valore da inserire ha un colore proprio, il valore con cui viene confrontato è evidenziato, e la parte ordinata è verde. A differenza del bubble sort e del selection sort, la parte verde non è definitiva: un valore più piccolo che arriva dopo può ancora inserirsi. Prova una lista quasi ordinata per vedere quanto sono brevi le passate, poi una inversa.
Domande frequenti
Qual è la complessità temporale dell'insertion sort?
O(n²) nel caso peggiore e medio, e O(n) nel caso migliore, una lista già ordinata. Più precisamente, richiede un tempo proporzionale a n più il numero di inversioni. Usa solo O(1) di memoria aggiuntiva.
Che differenza c'è tra insertion sort e selection sort?
Il selection sort scorre tutta la parte non ordinata per trovare il valore più piccolo, quindi fa sempre n(n − 1)/2 confronti ma pochi scambi. L'insertion sort prende il valore successivo così come viene e lo sposta indietro solo quanto serve, quindi fa meno confronti, soprattutto sulle liste quasi ordinate, ma più scambi.
Cos'è il binary insertion sort?
Una variante che trova il posto del nuovo valore con una ricerca binaria nella parte ordinata, con circa log n confronti invece di fino a n. I valori vanno comunque spostati per fare spazio, quindi il numero di spostamenti, e il caso peggiore O(n²), restano gli stessi.
L'insertion sort è stabile?
Sì. Un valore torna indietro solo oltre valori strettamente più grandi, quindi i valori uguali mantengono il loro ordine originale.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova l'insertion sort