Insertion sort

In modo più specifico, nell’algoritmo di insertion sort si parte dall’elemento più a sinistra e si procede verso destra. Non appena si trova un elemento che è più piccolo rispetto a quelli alla sua sinistra, si spostano tutti gli elementi uno a uno verso destra in modo da creare lo spazio necessario per inserire il valore corrente nella posizione corretta. Quindi, se abbiamo un array [0, 2, 4, 1, 10, 8] e stiamo analizzando il valore 1, sposteremo prima 4, poi 2 verso destra, per poi collocare 1 tra 0 e 2. In questo modo si ottiene [0, 1, 2, 4, 10, 8]. Si passa quindi all’elemento successivo 10. In questo caso non bisogna fare nulla, perché è più grande di tutti gli elementi a sinistra. Poi si prende 8, e si sposta 10 a destra per assicurarsi che 8 sia posizionato tra 4 e 10.

a = [...]
for i in range(1, len(a)):              # inizia dal secondo elemento
    while i > 0 and a[i] < a[i - 1]:    # finché l’elemento corrente è più piccolo
        a[i - 1], a[i] = a[i], a[i - 1] # sposta l’elemento corrente con il precedente
        i -= 1                          # aggiorna l’indice dell’elemento corrente
print(a)