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.
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.
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
56 > 25=>[52, 25, 56, 69, 14, 3]52 > 25=>[25, 52, 56, 69, 14, 3]
- elemento target = 69
69 > 56=> nessuno spostamento
- elemento target = 14
69 > 14=>[25, 52, 56, 14, 69, 3]56 > 14=>[25, 52, 14, 56, 69, 3]52 > 14=>[25, 14, 52, 56, 69, 3]25 > 14=>[14, 25, 52, 56, 69, 3]
- elemento target = 3
(69 > 3)=>[14, 25, 52, 56, 3, 69](56 > 3)=>[14, 25, 52, 3, 56, 69](52 > 3)=>[14, 25, 3, 52, 56, 69](25 > 3)=>[14, 3, 25, 52, 56, 69](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 in Python
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.