Ordinamento per inserzione

6.1 Definizione dell'ordinamento per inserzione

Ordinamento per inserzione (Insertion Sort) è un algoritmo di ordinamento che costruisce un array (o lista) ordinato uno elemento alla volta. Prende ogni elemento dalla parte non ordinata e lo inserisce nella posizione corretta della parte ordinata.

Principio di funzionamento:

1. Iniziamo dal secondo elemento dell'array (il primo elemento è considerato ordinato).
2. Confrontiamo l'elemento corrente con i precedenti e lo spostiamo a sinistra fino a trovare la posizione corretta.
3. Ripetiamo il processo per tutti gli elementi dell'array, inserendo ogni nuovo elemento nel posto corretto della parte ordinata dell'array.

Complessità temporale e spaziale dell'ordinamento per inserzione

Complessità temporale:

• Nella peggiore delle ipotesi: O(n^2) — accade quando gli elementi sono inizialmente ordinati in ordine inverso.
• Nel caso medio: O(n^2) — avviene per una disposizione casuale degli elementi.
• Nella migliore delle ipotesi: O(n) — avviene quando gli elementi sono già ordinati.

Complessità spaziale:

O(1) — poiché l'algoritmo utilizza una quantità costante di memoria aggiuntiva (solo alcune variabili per memorizzare valori temporanei).

6.2 Analisi del funzionamento dell'algoritmo

In ogni fase dell'algoritmo abbiamo la seguente situazione:

• Abbiamo un elemento corrente con indice i.
• Tutti gli elementi a sinistra di esso sono già ordinati dal minore al maggiore.
• Cerchiamo di inserire il nostro elemento corrente nella parte ordinata dell'array in modo che l'ordine di ordinamento non venga interrotto.

Tentativo di inserire l'elemento nella parte ordinata dell'array appare così:

1. La variabile j nel ciclo assume valori da i - 1 a 0.
2. Se l'elemento corrente (i-esimo) è minore di quello j-esimo, allora spostiamo il valore dell'elemento j-esimo di 1 a destra.

Esempio: situazione corrente:

• Gli elementi evidenziati in verde sono già ordinati.
• In rosa — elementi che non sono ancora stati ordinati.
• L'elemento corrente all'indice 5 è evidenziato in marrone.

Proviamo a trovare il posto giusto per il nostro elemento corrente nella parte ordinata dell'array.

Passo 1 — memorizziamo il valore dell'elemento corrente nella variabile key.

Passo 2 — l'elemento No4 è maggiore di key? (10 è maggiore di 5?) Allora spostiamo l'elemento No4 a destra:

Passo 3 — l'elemento No3 è maggiore di key? (8 è maggiore di 5?) Allora spostiamo l'elemento No3 a destra:

Passo 4 — l'elemento No2 è maggiore di key? (6 è maggiore di 5?) Allora spostiamo l'elemento No2 a destra:

Passo 5 — l'elemento No1 è maggiore di key? (4 è maggiore di 5?) No. Allora mettiamo l'elemento key al posto dove era l'elemento No2.

Dopo aver inserito l'elemento No5 nel posto giusto, passiamo all'elemento No6 e cerchiamo di trovare la sua posizione nella parte ordinata dell'array:

Poi prendiamo il settimo elemento:

Poi l'ottavo:

6.3 Implementazione dell'algoritmo di ordinamento per inserzione

Ecco come appare questo algoritmo in Python:

def insertion_sort(arr):
    # Passiamo attraverso tutti gli elementi dell'array, a partire dal secondo
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # Spostiamo gli elementi arr[0..i - 1], che sono maggiori del key, di una posizione avanti while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
        arr[j + 1] = key # Inseriamo il key nella posizione corretta
    return arr  # Ritorniamo l'array ordinato
        
# Esempio di utilizzo:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Array ordinato:", sorted_arr)
# Output: Array ordinato: [5, 6, 11, 12, 13]

Spiegazione:

• Memorizziamo l'elemento corrente in key
• Spostiamo tutti gli elementi della parte ordinata dell'array a destra
• Inseriamo il nostro elemento nel posto adatto

Esempio di funzionamento dell'algoritmo

Prendiamo un esempio di array: [12, 11, 13, 5, 6]

1. Primo passaggio (i = 1):

• Confrontiamo 11 e 12, spostiamo 12 a destra.
• Array: [11, 12, 13, 5, 6]

2. Secondo passaggio (i = 2):

• 13 è già al suo posto.
• Array: [11, 12, 13, 5, 6]

3. Terzo passaggio (i = 3):

• Confrontiamo 5 con 13, 12 e 11, spostiamo tutti a destra.
• Array: [5, 11, 12, 13, 6]

4. Quarto passaggio (i = 4):

• Confrontiamo 6 con 13, 12 e 11, spostiamo tutti a destra.
• Array: [5, 6, 11, 12, 13]

L'algoritmo si conclude, poiché tutti gli elementi sono ordinati.