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

Sito: 7ecnologie

Sezione: 10. Algoritmi e strutture dati

Capitolo: 01. Tipi base

Paragrafo: 01. Ordinamento per inserimento

Indice dei capitoli: 00. Risorse - 01. Tipi base - 02. Strutture lineari dinamiche - 03. Alberi e grafi

Indice dei paragrafi: 01. Ordinamento per inserimento