Ordinamento per inserimento
Costruisce una parte ordinata a sinistra, un valore alla volta. Ogni nuovo valore viene estratto e spostato a sinistra finché non incontra un valore più piccolo.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- sì
- sì
Caso migliore: come cresce il tempo con la dimensione n della lista quando l'input è il più facile per questo algoritmo.
Caso medio: crescita tipica del tempo con n. Con n², raddoppiare il numero di valori quadruplica circa il tempo; n log n cresce molto meno.
Caso peggiore: la crescita sull'input più difficile. Utile quando la velocità non deve mai calare.
Spazio: quanta memoria extra serve oltre alla lista. 1 vuol dire poche variabili, n una copia della lista.
Stabile: due valori uguali mantengono il loro ordine originale. Conta quando si ordinano record in base a un solo campo.
Sul posto: ordina dentro la lista stessa, senza una seconda lista.
- confronto
- spostamento
- in mano
- parte ordinata
- al suo posto finale
Prova così: Scegli una lista quasi ordinata. Non si sposta quasi niente, quindi finisce in pochissimi passi.
Come funziona
La parte sinistra è sempre ordinata. Si estrae il valore successivo, si sposta di una posizione a destra ogni valore più grande della parte ordinata, poi si mette il valore nel vuoto. È così che molti ordinano le carte che hanno in mano.
Quando conviene usarlo
Una buona scelta per liste corte e per liste quasi ordinate, dove è molto veloce. Le vere librerie di ordinamento lo usano per i pezzi piccoli della lista, dentro metodi più veloci.