Esercizi di programmazione in Pascal->MergeSort

MergeSort

In questo piccolo tutorial verrà spiegato l'implementazione del classico ordinamento MergeSort. Dato un vettore di elementi da ordinare, l'algoritmo si basa sulla suddivisione ricorsiva del vettore in due sotto-vettori da ordinare. Alla fine di ogni passo ricorsivo, i sotto-vettori ordinati vengono fusi in un vettore in modo da risultare ordinato. Quest'ultimo costituisce il sotto-vettore ordinato del passo ricorsivo superiore.

Di seguito la definizione del vettore da ordinare e la variabile contenete il vettore:
La procedura seguente esegue la fusione di due vettori. Come accennato prima, i due vettori sono ordinati, quindi è relativamente semplice fonderli in un unico vettore ordinato.
Come si vede nel codice, i vettori sono indicati mediante degli indici: "p", "q" ed "r" del vettore B. Cioè il primo vettore corrisponde agli elementi [p, q] ed il secondo vettore corrisponde agli elementi [q+1, r]. Il risultato viene memorizzato in A nell'intervallo [p, r]. Passando il vettore A per valore alla funzione Merge(), in pratica ne otteniamo una copia in modo da modificare tranquillamente il vettore A. Vediamo il codice:
In questa procedura possiamo vedere come viene implementato il passo ricorsivo. La procedura riceve gli indici "p" ed "r" ad indicare il vettore A nell'intervallo [p, r]. I due passi successivi sono dunque quelli di eseguire la ricorsione spezzando il vettore in due sotto-vettori con intervallo [p, q] per il primo e [q+1, r] per il secondo. Come ultimo passo viene richiamata la procedura di fusione dei due vettori Merge().
Vediamo il codice:
Da notare che la prima chiamata alla proedura M_Sort() deve corrisponde a tutto il vettore, quindi all'intervalo [1, n] di A.
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 (543 byte)