L'algoritmo di Insertion Sort consente di ordinare una lista di elementi omogenei con prestazioni che diminuiscono al crescere del numero di elementi. L'algoritmo è leggermente più sofisticato del Bubble Sort, tuttavia nel caso peggiore offre delle prestazioni mediocri.

È opportuno quindi utilizzarlo con pochi elementi presenti nella lista.

Strategia

La strategia adottata dall'algoritmo prevede lo spostamento dell'elemento obiettivo(target_element) nella posizione corretta. Quindi ad ogni iterazione si possono avere x - 1 spostamenti, dove x rappresenta l'indice dell'elemento corrente.

Algoritmo

L'algoritmo Insertion Sort apporta qualche ottimizzazione rispetto all'algoritmo Bubble Sort, poiché ad ogni iterazione si potranno avere un numero di scambi ridotti, qualora la lista fosse già parzialmente ordinata. Quando l'elemento corrente risulta maggiore di un qualsiasi elemento precedente, l'esecuzione dell'iterazione è interrotta poiché la sottolista [0, ..., elemento_target] risulta ordinata.

Volendo ordinare la lista [56, 52, 25, 69, 14, 3], le iterazioni saranno le seguenti:

• lista iniziale: [56, 52, 25, 69, 14, 3]
• elemento target = 52
  • 56 > 52 => [52, 56, 25, 69, 14, 3]
• elemento target = 25
  1. 56 > 25 => [52, 25, 56, 69, 14, 3]
  2. 52 > 25 => [25, 52, 56, 69, 14, 3]
• elemento target = 69
  • 69 > 56 => nessuno spostamento
• elemento target = 14
  1. 69 > 14 => [25, 52, 56, 14, 69, 3]
  2. 56 > 14 => [25, 52, 14, 56, 69, 3]
  3. 52 > 14 => [25, 14, 52, 56, 69, 3]
  4. 25 > 14 => [14, 25, 52, 56, 69, 3]
• elemento target = 3
  1. (69 > 3) => [14, 25, 52, 56, 3, 69]
  2. (56 > 3) => [14, 25, 52, 3, 56, 69]
  3. (52 > 3) => [14, 25, 3, 52, 56, 69]
  4. (25 > 3) => [14, 3, 25, 52, 56, 69]
  5. (14 > 3) => [3, 14, 25, 52, 56, 69]

Come si evince dall'esempio, l'algoritmo ad ogni iterazione sposta l'elemento considerato nella posizione corretta della sottolista ordinata, tralasciando il seguito della lista che può ancora non essere ordinata. Al termine dell'esecuzione avremo tutta la lista ordinata.

Implementazione

Una possibile implementazione dell'algoritmo Insertion Sort in Python è la seguente:

def insertion_sort(elements):
    for target_index in range(1, len(elements)):
        current_index = target_index - 1
        target_element = elements[target_index]
        current_element = elements[current_index]
        while( (current_element > target_element) and 
            (current_index >= 0) ):
            print(f"{elements[current_index]} > {target_element}")
            elements[current_index+1] = current_element
            elements[current_index] = target_element
            current_index -= 1
            current_element = elements[current_index]
        print(elements)
    return elements

Prestazioni

Nel valutare le prestazioni dell'algoritmo Insertion Sort dobbiamo fare dei distinguo.

Se la lista è ordinata, l'algoritmo impiega un tempo di esecuzione lineare pari a O(n).

Se la lista non è ordinata, allora le prestazioni cambiano notevolmente. Se infatti la lista prevede ad ogni iterazione lo spostamento del current_element, si ha un tempo di esecuzione quadratico pari a O(n²).

Conclusioni

L'algoritmo Insertion Sort, così come l'algoritmo Bubble Sort, devono essere utilizzati per input molto piccoli poiché al crescere dell'input le prestazioni decadono notevolmente.

Altri articoli

Gestione dei turni di lavoro

Gestire Python virtualenv con pyenv su Linux

Risolvere errore uploader id su youtube-dl

VIM come IDE di sviluppo in Python