Insertion Sort in Python

Questo video accompagna la guida Insertion Sort in Python e riprende i passaggi principali con una spiegazione più diretta e visuale.

Sintesi del video

Insertion Sort è un algoritmo di ordinamento che consente di ordinare gli elementi in modo più sofisticato del Bubble Sort.

Punti trattati

• Strategia
• Algoritmo
• Implementazione
• Prestazioni

Testo di supporto

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.

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
  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]

Approfondimento scritto

Per comandi, esempi e passaggi completi puoi leggere l’articolo collegato: Insertion Sort in Python .