1
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.
2
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:
3
513 752 623 264 54 415 376 157
0
1
2
3
4
5
6
7
352 57 62 267
451 143 374 15
0
4
1
2
3
5
6
7
35 75
26 26
45 415
731 153
0
2
4
6
1
3
5
5
7
6
2
5
4
3
0
1
2
3
4
5
6
7
1
7
4
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.
5
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
6
Sort(0,7)
Sort(0,3)
Sort(4,7)
Sort(0,1)
Sort(4,5)
Sort(2,3)
Sort(6,7)
5
3 752 623 642 54 415 376 157
1
0 1 2 73 4 5 6 7
523 75 62 267
0
1
2
514 413 374 15
4
3
5
53 57 3 62 26
54 415
0
4
1
2
3
5 1
7
6 2 2
0
1
2
3
6
7
6
31
7 153
5
6
5 4 4
3 5
4
5
6
7
1
7
7
// Mergesort
#include <iostream>
#include <cstdlib>
#include "InsertArray.h"
using namespace std;
// PROTOTIPI
void SortIt(int, int, int [], int);
void Update(int [],int &, int &);
void Merge(int, int, int, int [], int);
// DEFINIZIONI
void 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 "<<en
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");
}
8
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
9
Sort(0,7)
0
1
2
3
4
5
6
7
5
7
6
2
5
4
3
1
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
5 7
Sort(0,3)
Sort(4,7)
Sort(0,1)
Sort(2,3)
Sort(4,5)
Sort(6,7)
1 2 3 4 5 5 6 7
0
1
2
0
3
4
3
5
4
0
7
Stack della ricorsione
6
7
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);
10 }
Merge(Lo,Mid,Hi,AnArray);
};
Svantaggi del Merge-Sort
Necessita di un vettore di appoggio
Effettua gli spostamenti anche se il vettore di partenza è già ordinato
11
Complessità del MERGE-SORT
I 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
351 572 623 624 54 145 376 157
0
1
2
3
4
5
6
7
352 57 62 267
0
1
2
451 143 3
7
5
4 1
4
3
5
7
6
53 75
62 26
54 415
317 153
0
2
4
6
1
3
5
5
7
6
2
5
4
3
0
1
2
3
4
5
6
Livello
N° Array
0
1
20
N° passi = K*N
1
2
21
……
……..
….
dove K=log2N
K
N
2k
7
1
7
12
Esercizio
Dato un Array del tipo
FIGLIO
PADRE
MADRE
M
U
R
A
G
M
G
C
N
C
B
P
U
I
G
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
13
// PROTOTIPI
void 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 );
// MAIN
int 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");
}
14
// DEFINIZIONI
char 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];
else
return 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);
else
return CercaNonno(a,x, Nfam,i+1,j);
Allegato: eserA
15
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.
TRUE
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
FALSE
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.
FALSE
TRUE
1
3
2
5
2
3
5
6
8
1
4
2
1
3
5
4
7
9
2
6
4
1
4
2
5
3
1
4
1
2
2
5
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;}
}
}
17
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
18
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 .
19