Algoritmo di ordinamento Insertion sort in C

L’insertion sort, detto anche algoritmo a inserimento, è un algoritmo di ordinamento che ordina una lista, o vettore, passando un elemento alla volta, analogamente a quando ordiniamo un mazzo di carte. 

Nonostante sia molto meno efficiente su vettori molto grandi rispetto ad algoritmi più avanzati, può avere alcuni vantaggi, tra i quali: è semplice da implementare, è più efficiente su data set più piccoli e già parzialmente ordinati, è più efficiente di altri algoritmi di ordinamento con complessità quadratica come il bubble sort e selection sort.

Funzionamento dell’algoritmo

Ad ogni iterazione l’insertion sort rimuove un elemento dalla sottosequenza non ordinata della lista e lo inserisce nella sottosequenza già ordinata, che inizialmente sarà composta da un unico valore. 

L’ordinamento avviene sul posto rimuovendo un elemento alla volta che verrà confrontato con il valore più alto contenuto nella sottosequenza ordinata. Se più grande rimane in quella posizione e l’algoritmo passa all’elemento successivo da ordinare, altrimenti lo inserisce nella posizione corretta all’interno della lista ordinata traslando di uno tutti i valori più grandi. Di conseguenza dopo k iterazioni la sottosequenza ordinata sarà composta da k elementi.

Fonte gif: Wikipedia

Per quanto riguarda la performance di insertion sort, possiamo osservare che:

• Il caso peggiore si presenta quando la lista è ordinata all’incontrario, quindi ogni elemento deve essere spostato dalla sua posizione iniziale al lato opposto della lista, in questo caso la complessità è O(n²).

• Il caso migliore è quando la lista è già ordinata, di conseguenza l’algoritmo presenta una complessità O(n).

Implementazione insertion sort in C

Per implementare in maniera corretta l’algoritmo abbiamo bisogno di due indici, uno che punta all’elemento da ordinare e uno all’elemento immediatamente precedente. Se l’elemento da ordinare è più grande dell’elemento precedente, i due vengono scambiati di posto e il processo viene ripetuto fino a che l’elemento non si trova nell'ordine giusto. Altrimenti se l’elemento da ordinare è più grande dell’elemento precedente, il primo indice punterà al prossimo elemento da ordinare, mentre il secondo indice punterà all’elemento immediatamente precedente.

Il ciclo while esterno deve partire dal secondo elemento (i=1), in quanto il primo elemento definisce già la sottosequenza ordinata. Mentre il ciclo while interno ha la funzione di confrontare l’elemento da ordinare con gli elementi contenuti nella sottosequenza ordinata, scambiando gli elementi che si trovano nell’ordine sbagliato.

#include <stdio.h>
#define N 10

int main(){
	int lista[N] = {4, 6, 12, 8, 3, 2, 5, 20, 1, 9};
	int i, j, temp;

	i = 1;
	while(i < N){
		j = i;
		while(j > 0 && lista[j - 1] > lista[j]){
			temp = lista[j - 1];
			lista[j - 1] = lista[j];
			lista[j] = temp;
			j--;
		}
		i++;
	}
	for(int k = 0; k < N; k++){
		printf("%d ", lista[k]);
	}

	return 0;
}
// Output: 1 2 3 4 5 6 8 9 12 20