Array già ordinato: un confronto per ogni chiave e nessuno spostamento, quindi Θ(n).
Algoritmi di ordinamento · 1/7
Insertion sort
Costruisce una parte ordinata, un elemento alla volta.
Tempo medioΘ(n²)
MemoriaΘ(1)
StabileSì
In placeSì
Come funziona
La porzione a sinistra dell’indice corrente è sempre ordinata. Si estrae la chiave, si spostano a destra gli elementi maggiori e si inserisce la chiave nello spazio liberato.
Invariante: Prima dell’iterazione i, A[0…i−1] contiene gli stessi elementi iniziali ed è ordinato.
Simulazione passo passo
Ogni barra rappresenta un elemento. I colori distinguono gli elementi confrontati, il pivot o la chiave, la parte già definitiva e l’area attiva.
Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.
- Confronti
- 0
- Scritture
- 0
- Scambi
- 0
- Passaggio / livello
- 0
attivo
confronto
pivot / chiave
definitivo
Pseudocodice collegato alla simulazione
for i ← 1 to n − 1key ← A[i]j ← i − 1while j ≥ 0 and A[j] > keyA[j + 1] ← A[j]j ← j − 1A[j + 1] ← key
La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.
Studio della complessità
In media ogni chiave attraversa una frazione lineare del prefisso: Θ(n²) confronti e spostamenti.
Array in ordine inverso: 1 + 2 + … + (n−1) = n(n−1)/2 spostamenti, dunque Θ(n²).
Conserva solo chiave, indice e temporanei: Θ(1). È stabile perché sposta soltanto valori strettamente maggiori.
Proprietà in breve
La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.
La classificazione considera la versione dell’algoritmo mostrata in questa pagina.
Quando usarlo e che cosa evitare
Buona scelta quando…
Ottimo per array piccoli, quasi ordinati o ricevuti in streaming. È spesso usato come fase finale di algoritmi ibridi.
Errore comune
Usare ≥ nel confronto invece di > può invertire elementi uguali e perdere la stabilità.