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 confronti ed altrettanti spostamenti (mezzi scambi), che possono diventare il doppio nel caso peggiore.

Conclusioni

In questa lezione abbiamo studiato l’algoritmo insertion sort, nella prossima vedremo altri algoritmi di ordinamento.

Fate pure le vostre considerazioni nei commenti sotto.

Alcuni link utili

Indice tutorial linguaggio C

Array o vettori

Quick sort in linguaggio C

Merge sort in linguaggio C

Somma elementi diagonale principale di una matrice

Esercizio con le matrici in C

Triangolo di Tartaglia in C

Ricerca di un elemento in una matrice

Somma elementi appartenenti alla cornice esterna di una matrice

Cifrario di Cesare

Cifrario di Cesare da file

Numeri random in un file

Multipli di un numero su file