Ordinamento per inserimento

Il selection sort è anch’esso un tipo di tecnica di ordinamento con complessità temporale O(n²), ma è un po’ più ottimizzato del bubble sort.

In questo algoritmo, l’array viene suddiviso in due parti. Una è ordinata e l’altra è non ordinata. Scegliamo un elemento da un array non ordinato e lo inseriamo nell’array ordinato nella sua posizione corretta.

Ripetiamo il processo finché tutti gli elementi non sono ordinati.

1. Supponiamo di avere un array {8,4,1,5}. Consideriamo il primo elemento ordinato e tutti gli altri non ordinati. All’inizio, il 0° elemento è considerato ordinato.

2. Crea una variabile temporanea e inserisci il (i)-esimo elemento (in questo caso è 4). Confronta temp con l’array attualmente ordinato, che al momento contiene 8. Poiché 4<8, sposta l’array ordinato a destra finché 4 non raggiunge la sua posizione corretta. In questo caso, 8 deve essere spostato una volta. Ora la lunghezza dell’array ordinato è diventata 2.

3. Ripetiamo il processo finché l’intero array non è ordinato.

for(int i=1;i<n;i++){           //inizia dal primo elemento, poiché consideriamo già ordinato l'elemento 0th
    int temp=arr[i];
    
    int j=i-1;                  //per controllare tutti gli elementi alla sua sinistra 
    
    while(arr[j]>temp && j>=0){ //sposta gli elementi finché sono maggiori di temp, fino al primo elemento
      arr[j+1]=arr[j];          //sposta l'elemento di una posizione a destra
      j--;                      
    }
    
    arr[j+1]=temp;              //metti temp nella posizione corretta
  
}

Per visualizzare l’insertion sort

Visualizzatore dell’insertion sort