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.

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

#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]);
	}
		
}

Prestazioni

L’algoritmo utilizza una quantità minima di memoria indispensabile ma è lento con array di grosse domensioni, 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.

Alcuni link utili:

Array o vettori

Selection sort in C

Merge sort in C

Quick sort in C

Autore dell'articolo: Cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *