L'università è facile…

studia finché non lo diventa…

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:

image

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>.

image

Tempo di esecuzione:

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

Calcoliamo questa ricorrenza.

image

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

image

image

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

avatar firma

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Informazione

Questa voce è stata pubblicata il 21/06/2010 da in Algoritmi e strutture dati con tag , , , .
%d blogger hanno fatto clic su Mi Piace per questo: