Merge Sort

Ciao a tutti ,oggi si parla di un altro algoritmo di ordinamento che prende in input una sequenza di elementi e produce una sequenza ordinata in output. Di solito si usa l'array come struttura dati della sequenza.

Merge Sort si basa sul metodo divide e impera :

1.Divide:  divide la sequenza di n elementi da ordinare in due sotto sequenze di (n/2) elementi ciascuno.

2.Impera: ordina le due sotto sequenze in modo ricorsivo con Merge sort

3.Combina: riunisce le due sequenze ordinate in una sequenza ordinata (soluzione del problema) con Merge.

Il caso elementare arriva quando la sotto sequenza da ordinare ha dimensione uno e quindi non c’è niente da fare perché in questo caso,la sotto sequenza è già ordinata.

Il punto fondamentale del nostro algoritmo rimane quindi la procedura Merge. Vediamo come funziona.

Analisi di Merge:

Immaginate di dover riunire due pacchetti  di carte già ordinate in un solo pacchetto che deve essere anche lui ordinato.

Intuitivamente si procede in questo modo.

1- Si prende la più piccola carta fra le due prime carte dei pacchetti iniziali (che rappresentano il minimo per ogni pacchetto). Si mette la carta presa nel terzo pacchetto.

2.Si ripete il passo 1 finche l’uno dei due pacchetti non si esaurisce.

3.se uno dei pacchetti è esaurito,si prende le carte del pacchetto rimanente e gli si mette nel terzo pacchetto nello stesso ordine.

Merge esegue il processo appena descritto.

Analisi di Merge Sort:

Ecco lo pseudo codice di Merge Sort:

Spiegazioni:

A è l’array rappresenta la sequenza da ordinare,p è l’indice del primo elemento e r l’indice dell’ultimo elemento.

Se p>=r ,l’array A[p…r] contiene al massimo un elemento e come detto prima è gia ordinato.

Nel caso contrario (p < r ):

- Si divide A[p..r] a metta in 2 array A[p..q] e A[q+1..r]

-Si impera A[p..q] e A[q+1..r] con Merge Sort

-Si combina  A[p..q] e A[q+1..r] con Merge

Esempio pratico:

Merge Sort è applicato all'array A=<5,2,4,6,1,3,2,6>.

Tempo di esecuzione:

Questo algoritmo è ricorsivo ,quindi il suo tempo di esecuzione è una ricorrenza.

Calcoliamo questa ricorrenza.



Nel peggior caso ,avremmo un tempo di esecuzione T(n) definito cosi:





Grazie di aver letto l’articolo. Dubbi ,domande e suggerimenti ?Lo spazio per i commenti è qui sotto.

Ti è piaciuto l'articolo..?

Ricevi gli aggiornamenti via mail:	Seguici!