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.

Algoritmi Algoritmi Ordinamento Linguaggio C