Nel frammento di codice sottostante viene presentato l’algoritmo di ordinamento Insertion Sort. L’algoritmo Insertion Sort scandisce l’intero vettore di elementi, eseguendo ogni volta il confronto tra il valore da inserire e il valore attualmente in esame. Una volta trovata la posizione corretta l’algoritmo inserisce il nuovo valore nella posizione successiva a quella trovata.
#include <stdlib.h> #include <stdio.h> void stampa(int *a, int n); void insertionSort(int *a, int n); int main(void) { int a[10] = {5, 1, 3, 99, 45, 63, 21, 34, 0, 84}; // elementi da ordinare int n = 10; // numero di elementi stampa(a, n); insertionSort(a, n); stampa(a, n); return 1; } // stampo tutti i valori presenti nel vettore void stampa(int *a, int n) { int i; for(i=0; i<n; i++) printf("%d ", a[i]); printf("\n"); } // passo alla funzione il puntatore al vettore da ordinare e la sua dimensione void insertionSort(int *a, int n) { int b, i, j; // scorro tutti gli elementi del vettore, dal secondo all'ultimo for(i=1; i<n; i++) { b = a[i]; // seleziono il primo elemento utile j = i - 1; /* confronto l'elemento con i precedenti, se trovo un numero con indice inferiore e valore superiore lo inserisco al posto dell'elemento selezionato */ while(j>=0 && b<a[j]) { a[j+1] = a[j]; // sposto in avanti il valore selezionato j = j - 1; } a[j+1] = b; // completo lo scambio inserendo b al posto dell'ultimo numero scambiato // ad ogni ciclo di esegue uno shift degli elementi in avanti } }
Notiamo che il ciclo for parte dal valore 1, e non dal valore 0, in questo modo il primo componente del vettore (a[0]) viene utilizzato come vettore di confronto (a se stante), giĆ ordinato, mentre i successivi valori (a[i]) vengono considerati come gli input da ordinare. Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.