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.

Capire Insertion Sort

Oggi vediamo più in dettaglio l’algoritmo di ordinamento per inserimento.

Come richiesto da l’Algor method ,eseguiro 4 passi.

1.Il Problema

Ordinare dei dati omogenei (dello stesso tipo) o in ordine crescente o decrescente dipendendo dell’applicazione specifica.

2.Struttura dati usata

Di solito si usa un array di interi. Ma questo può variare nelle applicazioni specifiche.

3.Pseudo codice

Praticamente l’algoritmo si comporta come un umane che vuole ordinare una mano di carta. Al ’inizio , tutte le carte sono sul tavolo,con la mono destra prendo una a una le carte e le metto sulla mano sinistra nel posto giusto. Per mettere la carta nel posto giusto ogni volta ,faccio un paragono con le carte della mano sinistra. Ora che sappiamo come fa l’algoritmo ,ecco lo pseudo codice :

INSERTION-SORT(A)

1. for j <– 2  to length[A]
2.      do   key <– A[J]
3.               // inserire A[j] nella sequenza ordinata A[1..j -1]
4.               i <– j – 1
5.               while i>0 and A[i]>key
6.                   do A[i + 1] <– A[i]
7.                         i <– i – 1
8.               A[i + 1] <– key

Notiamo che l’ordinamento usa un solo array per questo si parla di ordinamento in place.

Key rappresenta la nuova carta da inserire ogni volta nella mano sinistra.

A[1..j-1] rappresenta la mano sinistra cioè la parte de l’array già ordinata.

J serve ad indicizzare la variabile da inserire in A[1..j-1]

I permette di scorrere A[1..j-1] cioè da j-1 a 1.

il primo ciclo While è quello che fa prendere ogni volta una variabile key da inserire dentro A[1..j-1].

il secondo ciclo invece è quello che fa trovare il posto giusto a key paragonandolo ogni volta ad un elemento di A[1..j-1].

Ora che abbiamo capito come funziona l’algoritmo attraverso questo pseudo codice calcoliamo la complessità

4.Complessità

Per calcolare la complessità ,dobbiamo calcolare quante volte viene eseguita una istruzione. un istruzione presente in un ciclo viene eseguita un numero di volte pari a quanti indici il ciclo coinvolge con il contatore. Se associamo una costante cj ad ogni istruzione ,otteniamo qualcosa di questo tipo:

La somma è quindi  c1*n+c2*(n – 1) + c4*(n – 1) + c5*£ + c6*(£ – 1) + c7*(£ – 1)     + c8*(n – 1)

Ora vediamo di calcolare £. Il ciclo dalla riga 5 alla 7 va dell’indice 1 a j – 1, quindi il costo di ogni riga di questo ciclo diventa cj*(j – 1). Ma ognuna di queste righe si trovano nel grande ciclo che va dalla prima all’ultima riga  (indice coinvolti sono di n – 1); quindi

Questo ci da un risultato dell’ordine di

Conclusione  La somma totale è circa

La complessità nel caso peggiore è quindi  una forma quadratica.

Spero che hai imparato qualcosa leggendo questo articolo. Se hai dei dubbi o suggerimenti,lasca un commento qui sotto.