Esercizi di programmazione in Pascal->Insertionsort

Insertionsort

In questo piccolo tutorial verrà spiegato l'implementazione del classico ordinamento Insertionsort.
Questo algoritmo è utile per ordinare un basso numero di elementi, in quanto molto semplice da implementare anche se non è molto efficente.
Dato un vettore di elementi da ordinare, l'algoritmo si basa sull'idea di inserire un elemento per volta in un'altro vettore e di sistemarlo in modo da avere un vettore ordinato. Ogni nuovo elemento viene inserito alla fine, e successivamente viene fatto scalare con tutti gli elementi più grandi di lui.

Di seguito la definizione del vettore:
Nella procedura di seguito possiamo vedere che l'indice "j" viene utilizzato per "suddividere" il vettore A, dove la prima parte rappresenta il vettore ordinato mentre la seconda rappresenta il vettore da ordinare.
Ad ogni passo del ciclo "for", viene preso l'elemento A[j] (della seconda parte del vettore) e viene fatto scalare nela prima parte del vettore mediante il ciclo "while". Alla fine di ogni ciclo la prima parte del vettore acquisisce un nuovo elemento dalla seconda pur rimando ordinata. Alla fine si ottine un vettore completamente ordinato.

Vediamo il codice:

Il corpo del programma crea un vettore con numeri generati casualmente, richiama la procedura di ordinamento e quindi stampa il risultato.
Vediamo di seguito il codice.



Scarica sorgente (397 byte)