01. Ordinamento per inserimento

L'algoritmo di ordinamento per inserimento, detto insertion sort, opera su un array di N elementi, posizionati nelle celle che vanno da 0 a N-1.

    • L'algoritmo esegue N-1 passi.

    • In partenza il primo elemento ad essere analizzato è quello in posizione 1 ed è confrontato con l'unico elemento che precede. Al termine della prima iterazione risulteranno orinati tra loro i primi due elementi (posizioni 0 e 1).

    • Al generico passo i = 1, 2, ... N-1 l'elemento in posizione i viene inserito al posto giusto tra gli elementi che occupano le posizioni 0 ... i. Ad esempio al passo 6 (cioè quando i vale 6) gli elementi che occupano le posizioni da 0 ... 6 sono tra loro ordinati. I restanti elementi non essendo stati ancora analizzati non rispettano alcun ordinamento. Nell'algoritmo la variabile prossimo è utilizzata per denotare l'elemento in posizione i. Questo elemento è confrontato con gli elementi che occupano una posizione più piccola di i fino a trovare la giusta posizione. Si procede come il gambero a marcia indietro.

    • Ogni elemento che precede, se più grande di prossimo, è spostato di una posizione in avanti (cioè verso destra) per far posto al nuovo elemento

    • In ultimo, nel posto appena creato, viene inserito l'elemento prossimo.


  • Codice sorgente linguaggio C

#include <stdio.h>


void InsertionSort(int a[], int N)

{

int prossimo, i, j;

for (i = 1; i < N; i = i+1) {

prossimo = a[i];

j = i;

while ( (j > 0) && (a[j-1] > prossimo) ) {

a[j] = a[j-1];

j = j - 1;

}

a[j] = prossimo;

}

}


int main()

{

#define N 10

int a[N]={10, 15, 17, 9, 3, 7, 11, 2, 8, 99}, i;


printf("InsertionSort: programma di prova\n");


printf("\nArray di partenza da ordinare:\n");

for (i=0; i<N; i++)

printf("%d ", a[i]);


InsertionSort(a, N);


printf("\n\nArray ordinato: \n");

for (i=0; i<N; i++)

printf("%d ", a[i]);



return 0;

}


  • Esecuzione:

InsertionSort: programma di prova


Array di partenza da ordinare:

10 15 17 9 3 7 11 2 8 99


Array ordinato:

2 3 7 8 9 10 11 15 17 99