1

2

MERGE - SORT

Un algoritmo di sort classico ha in genere una complessità di calcolo pari a O(N2).

Vediamo un algoritmo che, fondato sul criterio del DIVIDE ET IMPERA, ha una complessità più bassa.

Il merge-sort è fondato sul principio ricorsivo di ridurre il problema di partenza di un fattore 2 e nessun processo ricorsivo attivato viene fatto più di una volta.

3

Merge-sort.

Dato un array A di dimensioni N, che si vuole

ordinare, lo si suddivide in due sub-array ciascuno di

dimensioni N/2. I due sub-array così ottenuti vengono

a loro volta divisi a metà. Il processo termina quando

ogni sub-array prodotto contiene un solo elemento.

Si consideri l’esempio seguente:

4

3 5 2 6 4 1 7 50 1 2 3 4 5 6 7

1 2 3 4 5 5 6 7

0 1 2 3

3 5 2 6 4 1 7 52 5 6 7 1 3 4 54 5 6 7

53 62 14 5775 62 54 310 1 2 3 4 5 6 7

475 6 2 5 3 12 30 1 4 5 6 7

3 5 2 6 4 1 7 50 1 2 3 4 5 6 7

5 7 6 2 5 4 3 1

0 1 2 3

3 5 2 6 4 1 7 55 7 6 2 5 4 3 14 5 6 7

53 62 14 5775 26 45 130 1 2 3 4 5 6 7

475 6 2 5 3 12 30 1 4 5 6 7

5

Si parte con la richiesta di ordinare gli elementi dell’array compresi tra 0 e N, si riduce poi questo intervallo attraverso due variabili Lo e Hi fino a quando nel subarray non resta che un elemento. Questo è ovviamente ordinato e quindi si attiva la catena pop.

Per dividere i Subarrays usiamo una variabile locale Mid. Questi Subarrays saranno prima ordinati (sorted) o poi fusi (merged).

CASO BASE si ha quando i due subarrays sono ridotti ad una sola variabile cioè sono banalmente ordinati.

Quando si arriva al Caso Base allora si attiva il processo di Merge tra i due arrays adiacenti rimasti.

Se invece siamo in presenza di subarrays con più di un elemento questo implica che il subarray deve essere ordinato.

6

Lo pseudo codice per l’algoritmo di sort è il seguente:

void SortIt(int Lo, Hi, int AnArray[]);

usa i valori degli indici in input (Lo,Hi) per dividere AnArray in due subarray (inferiore e superiore)

if gli indici del subarray inferiore implicano un array ordinabile SortIt(usa come indici quelli del subarray inferiore ,AnArray)

if gli indici del subarray superiore implicano un array ordinabile

SortIt(usa come indici quelli del subarray superiore ,AnArray)Inizialmete avremo: SortIt(0, N-1, AnArray)

Di seguito si mostra l’albero ricorsivo per un array di 8 elementi

7

Sort(6,7)

Sort(4,5)

Sort(4,7)

Sort(2,3)

Sort(0,1)

Sort(0,3)

Sort(0,7)

3 5 2 6 4 1 7 50 1 2 3 4 5 6 71 2 3 4 5 5 6 7

0 1 2 33 5 2 6 4 1 7 52 5 6 7 1 3 4 5

4 5 6 7

53 62 14 5775 62 54 310 1 2 3 4 5 6 7

475 6 2 5 3 12 30 1 4 5 6 7

3 5 2 6 4 1 7 50 1 2 3 4 5 6 75 7 6 2 5 4 3 1

0 1 2 33 5 2 6 4 1 7 55 7 6 2 5 4 3 1

4 5 6 7

53 62 14 5775 26 45 130 1 2 3 4 5 6 7

475 6 2 5 3 12 30 1 4 5 6 7

1

6

54

3

2

7

8

// Mergesort #include <iostream>#include <cstdlib>#include "InsertArray.h"using namespace std;// PROTOTIPIvoid SortIt(int, int, int [], int);void Update(int [],int &, int &);void Merge(int, int, int, int [], int);// DEFINIZIONIvoid SortIt(int Lo, int Hi,int AnArray[], int N){int Mid;Mid=(Lo+Hi)/2; if (Lo < Mid) {

SortIt(Lo,Mid,AnArray, N); } if ((Mid+1) < Hi) { SortIt(Mid+1,Hi,AnArray, N); }

Merge(Lo,Mid,Hi,AnArray, N);};

int main(){ int Lo=0;int Hi,N;cout<<" Quanti numeri vuoi ordinare? ";cin>>Hi;N=Hi;int AnArray[Hi];int I, Mid;cout<<"VETTORE DA ORDINARE "<<endl;for (I=0;I<Hi;I++)AnArray[I]=rand()%10;cout<<endl;StampaVettore (AnArray, N, 'A');SortIt(Lo,Hi-1,AnArray, N);cout<<" VETTORE ORDINATO\n"<<endl;StampaVettore (AnArray, N, 'A');system("pause");}

9

void Merge(int Lo,int Mid,int Hi, int AnArray[], int N){int Temp[N];int Index, I1, I2;I1=Lo; I2=Mid+1;for (Index=Lo;Index<=Hi;Index++) { if (I1 > Mid ) { Temp[Index]=AnArray[I2]; I2=I2+1; } else { if (I2 > Hi) { Temp[Index]=AnArray[I1]; I1=I1+1; } else {

if (AnArray[I1] < AnArray[I2]) { Temp[Index]=AnArray[I1];

I1=I1+1; } else {

Temp[Index]=AnArray[I2]; I2=I2+1; } } }} for (Index=Lo; Index<=Hi; Index++) AnArray[Index]=Temp[Index];}

Se è stata controllata tutta la prima metà allora aggiungi direttamente la seconda

Se è stata controllata tutta la seconda metà allora aggiungi direttamente la prima

Inserisci l’elemento più piccolo e incrementa opportunamente l’indice

Allegato mergesort

10

Sort(0,3)

Sort(0,7)

Sort(4,7)

Sort(4,5)Sort(6,7)

5 7 6 2 5 4 3 1

Sort(0,1)

mer

ge5 7

Sort(2,3)

5 7 2 6

2 5 6 7

2 5 6 7 4 5

2 5 6 7 4 5 1 3

2 5 6 7 1 3 4 5

1 2 3 4 5 5 6 7

void SortIt(int Lo, int Hi,int AnArray[]){ int Mid; Mid=(Lo+Hi)/2; if (Lo < Mid) {

SortIt(Lo,Mid,AnArray); } if ((Mid+1) < Hi) {

SortIt(Mid+1,Hi,AnArray); }Merge(Lo,Mid,Hi,AnArray);};

0 7

6 74 5

4 7

2 30 1

0 3

0 1 2 3 4 5 6 7

Stack della ricorsione

11

Svantaggi del Merge-Sort

Necessita di un vettore di appoggio

Effettua gli spostamenti anche se il vettore di partenza è già ordinato

12

Complessità del MERGE-SORTI livelli dell’albero di sort sono log N. Ad ogni livello dell’albero si fa un merge di N elementi, quindi in totale la complessità è data da N*log2 N

3 5 2 6 4 1 7 50 1 2 3 4 5 6 71 2 3 4 5 5 6 7

0 1 2 33 5 2 6 4 1 7 52 5 6 7 1 3 4 5

4 5 6 7

53 62 14 5775 62 54 310 1 2 3 4 5 6 7

475 6 2 5 3 12 30 1 4 5 6 7

3 5 2 6 4 1 7 50 1 2 3 4 5 6 75 7 6 2 5 4 3 1

0 1 2 33 5 2 6 4 1 7 55 7 6 2 5 4 3 1

4 5 6 7

53 62 14 5775 26 45 130 1 2 3 4 5 6 7

475 6 2 5 3 12 30 1 4 5 6 7

Livello N° Array  

0 1 20

1 2 21

…… …….. ….

K N 2k

N° passi = K*N

dove K=log2N

13

Esercizio

Dato un Array del tipo

Scrivere un programma che con due funzioni ricorsive dica:

1 - Dato X chi è il padre e la madre di X

2 - Dato X determini chi è il nonno e la nonna di Y

FIGLIO PADRE MADRE

M U R

A G M

G C N

C B P

U I G

14

// PROTOTIPIvoid leggi_dati(char[ ][3],int,int);void scrivi_dati(char[ ][3],int,int);char CercaPadre(char [ ][3], char , int ,int ,int );char CercaNonno(char [ ][3], char , int ,int ,int );

// MAINint main () { int rig=5; int col=3; char mat[5][3]; char X; cout<<"FIGLIO PADRE MADRE"<<endl; leggi_dati(mat,rig,col); scrivi_dati(mat,rig,col); cout<<"Dammi figlio ";cin>>X; cout<<"Il padre di "<<X<<" e' "<<CercaPadre(mat,X, rig,0,1)<<endl;; cout<<"La madre di "<<X<<" e' "<<CercaPadre(mat,X, rig,0,2)<<endl; cout<<"Il padre del padre di "<<X<<" e' "<<CercaNonno(mat,X, rig,0,1)<<endl; cout<<"La madre della madre di "<<X<<" e' "<<CercaNonno(mat,X, rig,0,2)<<endl; system("pause"); }

15

// DEFINIZIONIchar CercaPadre(char a[][3], char x, int Nfam,int i,int j)// determina chi è il padre di X}{ if (i>Nfam )

return 'i';else

if (a[i][0]==x) return a[i][j];elsereturn CercaPadre(a,x, Nfam,i+1,j);

}

char CercaNonno(char a[][3], char x, int Nfam,int i,int j)// determina chi è il genitore di X}{ if (i>Nfam )

return 'i';else

if (a[i][0]==x) return CercaPadre(a,a[i][j], Nfam,0,j);elsereturn CercaNonno(a,x, Nfam,i+1,j);

}

Allegato: eserAvi

16

Data una matrice di interi NxN scrivere una funzione

ricorsiva che valga TRUE se la somma degli elementi di

ogni riga è minore della riga precedente e la somma

degli elementi di ogni colonna è maggiore della somma

della colonna precedente, FALSE altrimenti.

1 3 2 5

8 1 4 2

7 9 2 6

5 3 1 4

2 3 6 5

1 3 5 4

4 1 4 2

2 1 2 5

TRUE

FALSE

17

1 3 2 5

8 1 4 2

7 9 2 6

5 3 1 4

2 3 5 6

1 3 5 4

4 1 4 2

1 2 2 5

TRUEFALSEData una matrice di interi NxN scrivere una funzione ricorsiva che valga TRUE se la somma degli elementi di ogni riga è minore della riga precedente e la somma degli elementi di ogni colonna è maggiore della somma della colonna precedente, FALSE altrimenti.

bool verifica (int a[][N], int N1, int &sr1,int &sr2,int &sc1,int &sc2,int i,int j){ if (i>=N1-1){cout<<"CONDIZIONI SODDISFATTE"<<endl;return true; }else if (j<N1) { sr1=sr1+a[i][j]; sr2=sr2+a[i+1][j]; sc1=sc1+a[j][i]; sc2=sc2+a[j][i+1]; verifica2(a,N1,sr1,sr2,sc1,sc2,i,j+1); } else { if ((sr2<sr1)&&(sc2>sc1)) { sr1=0;sr2=0;sc1=0;sc2=0; verifica2(a,N1,sr1,sr2,sc1,sc2,i+1,0); } else {cout<<"CONDIZIONI NON SODDISFATTE"<<endl; return false;} } }

18

ESERCIZIO

Scrivere un algoritmo ricorsivo per il calcolo della funzione booleana tale che assegnati due array di caratteri Sl e S2 restituisca TRUE se il secondo è contenuto tutto o in parte nel primo. FALSE altrimenti.

Esempio:

Se Sl=‘Smacchiare’ e S2=‘Macchia’ allora la funzione vale TRUE.

Se Sl='Mentecatto' e S2=’tatto' allora la funzione vale FALSE

stud ok

19

ESERCIZIO

• Date due matrici A(nxn) e B(nxn) di interi scrivere una

funzione ricorsiva booleana che calcoli la somma di tutti i

numeri contenuti in A sottratti a quelli contenuti in B e

dica se la differenza è negativa .