Benvenuto caro Lettore!

UF è un blog di ingegneria informatica pieno di articoli più o menoo tecnici. Iscriviti per rimanere aggiornato all'uscità dei prossimi articoli.

Ad Ad ads ads

Ricerca

21 giu 2010

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
Ti è piaciuto l'articolo..?

Ricevi gli aggiornamenti via mail:

Seguici!

0 commentaires:

Posta un commento

Ti è piaciuto l'articolo? Lascia un commento,fammi una domanda se hai dubbi o ambiguità.
Grazie!

Siamo su Facebook

Google+