Insertion Sort Python

Studiamo l’algoritmo Insertion Sort in Python, un algoritmo di ordinamento molto semplice da implementare.

L’algoritmo funziona in maniera molto simile al modo in cui sistemiamo in mano le carte da gioco.

Infatti si presuppone che la prima carta sia ordinata, dopo si prende una carta non ordinata e si posiziona alla sua sinistra se è minore, alla sua destra se è maggiore. In questo modo le carte non ordinate verranno messe al loro posto.

Come dicevamo, in modo molto simile funziona l’algortimo di ordinamento Insertion Sort.

Supponiamo, dunque, che la lista di partenza sia questa:

numbers = [3,6,1,9,2]

Si scorre la lista dalla posizione i che va da 1 fino ad n, quindi da numero 6 al numero 2.

Dunque se l’elemento della lista nella posizione i è maggiore del suo predecessore non si sposta, se invece è minore si sposta sulla sinistra finchè non si trova un precedessore più piccolo o si raggiunge la posizione più a sinistra dell’array.

Insertion Sort Python – code

Definiamo una funzione insertion_sort che prende come parametro la lista.

Creaimo un ciclo for che scorre gli elementi della lista da a 1 fino alla sua lunghezza, memorizziamo l’elemento da confrontare in una variabile temp e assegniamo a j l’elemento precedente dell’indice i.

Poi con un ciclo while continuiamo finchè l’elemento da confrontare è più piccolo dei predecessori o raggiunge la posizione più a sinistra (ovvero quella con indice 0). Di volta in volta scambiamo l’elemento e decrementiamo la variabile j.

Dopo il ciclo while, in ogni caso, assegniamo ad a[j+1] il valore di temp, anche se non ci sono stati scambi.

Ecco dunque il nostro codice dell’Insertion Sort in Python:


def insertion_sort(a):
    for i in range(1, len(a)):  
        temp = a[i] #primo elemento da confrontare
 
        j = i-1 #la prima volta è il primo elemento
        while j >= 0 and temp < a[j]:
                a[j+1] = a[j]
                j -= 1
        a[j+1] = temp
       
a = [3,6,1,9,2]
insertion_sort(a)
print(a)

Potremmo anche evitare l'utilizzo della variabile temporanea assegnando a j la variabile i. Ecco una possibile implementazione:



def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j - 1] > a[j]:
            a[j], a[j - 1] = a[j - 1], a[j]
            j -= 1
       
a = [3,6,1,9,2]
insertion_sort(a)
print(a)

Possiamo provare il nostro codice nell'editor sotto:

In questa lezione abbiamo sviluppato l'algortimo Insertion Sort in Python, nelle prossime studieremo altri arlgoritmi di ordinamento.

Lezione precedente: Selection Sort in Python

Lezione successiva: Merge Sort in Python