InsertionSort: Algoritmo di ordinamento

Algo1 Icon

InsertionSort: Algoritmo di ordinamento

1

L’ InsertionSort è uno degli algoritmi probabilmente più facili da capire che ci sono: esso si basa praticamente sullo stesso meccanismo che ci porta ad ordinare meccanicamente le carte mentre giochiamo.

InsertionSort, dall’ inglese ordinamento per inserimento, funziona infatti così:

Stiamo giocando ad un gioco di carte (scala 40 o poker). Peschiamo una carta e la teniamo in mano. Peschiamo una seconda carta e facciamo il confronto: questa è maggiore o uguale alla carta che avevamo? Maggiore, la mettiamo a destra, minore a sinistra.
Peschiamo una terza carta e la confrontiamo con le altre due e la inseriamo nel giusta posizione.

E’ effettivamente questo che fà l’ algoritmo di InsertionSort e per farlo, lo fà senza creare Array di supporto quindi In Place.

Lo spazio occupato infatti, è theta(1).

Nei casi peggiori e medio, il tempo di esecuzione è di O(n2) che è veramente inefficiente, ma si presta molto bene ad ordinare insiemi già quasi ordinati.

Esempio di esecuzione:

Vediamo un esempio con un array di numeri:

Array di Interi A: [1,4,5,3,2,]

Applichiamo l’algoritmo, di cui vedremo fra poco il codice, all’ array:

  1. [1, 4, 5, 3, 2] Seleziona il minimo e lo mette in prima posizione.
  2. [1, 2, 4, 5, 3] Cerca il secondo minimo (2) e lo mette in posizione A[1]
  3. [1, 2, 3, 4, 5] Cerca il terzo minimo (3) e lo mette nella posizione sucessiva A[2]
  4. [1, 2, 3, 4, 5] Cerca il quarto minimo (4) e lo mette nella posizione successiva A[3]
  5. [1, 2, 3, 4, 5] L’array è terminato, quindi ora è ordinato.

La parte in grassetto è quella ordinata ad ogni passo dell’ algoritmo.

Vediamo quindi uno pseudocodice dell’ algoritmo di ordinamento Insertion Sort:

for j=2 to array.length(): //scorro l'array per la sua lunghezza
 chiave = array[j]; //Prendo l'elemento j
 i=j-1; //Prendo il suo precedente
 while i>0 and A[i]>chiave //se il suo precedente è maggiore
     A[i+1]=A[i] //Scambio il successivo col precedente
     i=j-1 //Lo faccio per tutti i precedenti
     A[i+1] = chiave

Un’altra caratteristica, come potete ben notare, è la facilità di implementazione in praticamente qualsiasi linguaggio.

About the Author

Federico PonziStudente, Webmaster ed appassionato di tutto ciò che è informatico con una spruzzata di scienza.View all posts by Federico Ponzi

Leave a Reply