Insertion Sort in C, algoritmo di ordinamento insertion sort in C

In questa lezione svilupperemo l’algoritmo di ordinamento insertion sort in C.

L’insertion Sort è un algoritmo di ordinamento che utilizza lo stesso metodo che un essere umano usa per ordinare le sue carte in mano.

Dunque fa un tipo di ordinamento in loco, ovvero non crea un array di appoggio, risparmiando in questo modo memoria.

L’insertion Sort è un algoritmo molto semplice da utilizzare ma non ha una grande efficienza, se non in caso di array iniziali parzialmente ordinati.

L’algoritmo ha bisogno di due indici, uno che punta all’elemento da ordinare e l’altro a quello immediatamente precedente.

Il passo successivo consiste nel confrontare i due elementi, se l’elemento puntato dal secondo indice è maggiore del secondo gli elementi allora vengono scambiati.

Sviluppo dell’algoritmo Insertion Sort in C

Di seguito ecco l’algoritmo sviluppato in linguaggio C:

#include <stdio.h>

main(){
	int a[10]={10,4,2,6,7,11,9,23,8,9};
	int i,j,temp;
	
	for(i=0;i<10;i++){
		printf("%d \t", a[i]);
	}
	
	printf("\nadesso ordiniamo con insertion sort\n");
		
	for(i=1;i<10;i++){ 
            temp=a[i]; 
            j=i-1; 
            while(j>=0 && a[j]>temp){
		a[j+1]=a[j];		
		j--;		
	}
	a[j+1]=temp;
	}

	for(i=0;i<10;i++){
		printf("%d \t", a[i]);
	}
		
}

Come potete notare si utilizzano due indici i e j e una variabile temporanea dove memorizzare temporaneamente l’elemento con indice i.

Prestazioni dell’insertion sort

L’algoritmo utilizza una quantità minima di memoria indispensabile ma è lento con array di grosse dimensioni, invece con array di piccole dimensioni è l’algoritmo di ordinamento più veloce.

Effettua in media $N^{2}/4$ confronti ed altrettanti spostamenti (mezzi scambi), che possono diventare il doppio nel caso peggiore.