Post on 03-Feb-2020
1Antonio Virdis - 2019
Algoritmi e Strutture Dati
Lezione 2
Antonio Virdis
antonio.virdis@unipi.it
www.iet.unipi.it/a.virdis
2Antonio Virdis - 2019
Sommario
⚫ Merge Sort
⚫ Ordinamento STL
⚫ Gestione Liste
⚫ Esercizi
3Antonio Virdis - 2019
A metà
Size
Size/2 Size/2
4Antonio Virdis - 2019
A metà
Size
Size/2 Size/2
5Antonio Virdis - 2019
Unire gli array
6Antonio Virdis - 2019
1 4 9 12 27 2 3 5 6 8
iSx iDx
7Antonio Virdis - 2019
combinavoid combina( int arr[] , int start , int mid , int end )
{
// init Variabili di stato + buffer appoggio
while(1)
{
// se arr[iSx] più piccolo
{
// Inserisco arr[iSx]
}
// se arr[iDx] più piccolo
{
// Inserisco arr[iDx]
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
8Antonio Virdis - 2019
combinavoid combina( int arr[] , int start , int mid , int end )
{
int iSx = start , iDx = mid; // stato
std::vector<int> tempResult; // buffer
while(1)
{
if(arr[iSx] < arr[iDx])
{
tempResult.push_back(arr[iSx++]);
// CONDIZIONE USCITA
}
else
{
tempResult.push_back(arr[iDx++]);
// CONDIZIONE USCITA
}
}
// GESTISCO ULTIMI
// RICOPIO da buffer a arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Antonio Virdis - 2019
10Antonio Virdis - 2019
divideSize
Size/2 Size/2
Size/4 Size/4 Size/4 Size/4
11Antonio Virdis - 2019
Lista ordinata Triviale
12Antonio Virdis - 2019
Divide , Conquer , Combine
conquer ( int * arr , int start , int end )
{
int mid;
if( start<end )
{
mid = (start+end)/2; // DIVIDE
conquer( arr , start , mid ); // CONQUER
conquer( arr , mid+1 , end ); // CONQUER
combina( arr , start , mid+1 , end );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13Antonio Virdis - 2019
Divide , Conquer , Combine
void mergeSort( int * arr , int start , int end )
{
int mid;
if( start<end )
{
mid = (start+end)/2; // DIVIDE
mergeSort( arr , start , mid ); // CONQUER
mergeSort( arr , mid+1 , end ); // CONQUER
combina( arr , start , mid+1 , end );
}
}
1
2
3
4
5
6
7
8
9
10
11
14Antonio Virdis - 2019
Complessità mergesort
⚫ elementi
⚫ Livelli
⚫ Costo livello
( )l o g n 1+
n
( )( )n lo g n 1+
n
( )n lo g n n+
15Antonio Virdis - 2019
Complessità mergesort
( )( )n lo g n
16Antonio Virdis - 2019
BEST CASE WORST CASE
Worst Case Best Case Average Case
Merge Sort
Insertion Sort ( )2
n ( )2
n( )n
( )n lo g n ( )n lo g n ( )n lo g n
17Antonio Virdis - 2019
Ibrido
Size
Size/4 Size/4 Size/4 Size/4
Size/2 Size/2
18
Complessità?
• Tempo di esecuzione: worst vs best vs avg
• Memoria: in-place or not in-place?
Antonio Virdis - 2019
19Antonio Virdis - 2019
Test
⚫ Insertionsort
⚫ Mergesort
⚫ Casi
⚫ Random
⚫ Ordinata
⚫ Inversa
⚫ Variare quantità linearmente (10 , 40 , 80…)
20Antonio Virdis - 2019
Where isWally?
21Antonio Virdis - 2019
22Antonio Virdis - 2019
23Antonio Virdis - 2019
Find Bug-Wally[..]
int iSx = start , iDx = mid;
int stop , iRim;
std::vector<int> tempResult;
while(1)
{if(arr[iSx] < arr[iDx]);
{tempResult.push_back(arr[iSx++]);
if(iSx == mid)
{ iRim = iDx;
stop = end;
break;}
continue;
}if(arr[iSx] >= arr[iDx])
{tempResult.push_back(arr[iDx++]);
if(iDx == end+1)
{ iRim = iSx;
stop = mid;
break;
}
[..]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Antonio Virdis - 2019
25Antonio Virdis - 2019
Compiler Flags
⚫ g++ -W -o test test.cpp
⚫ g++ -Wall -W -o test test.cpp
Antonio Virdis - 2019
Warning: suggest braces around empty body in an ‘if’ statement
27Antonio Virdis - 2019
Find Bug-Wally[..]
int iSx = start , iDx = mid;
int stop , iRim;
std::vector<int> tempResult;
while(1)
{if(arr[iSx] < arr[iDx]);
{tempResult.push_back(arr[iSx++]);
if(iSx == mid)
{ iRim = iDx;
stop = end;
break;}
continue;
}if(arr[iSx] >= arr[iDx])
{tempResult.push_back(arr[iDx++]);
if(iDx == end+1)
{ iRim = iSx;
stop = mid;
break;
}
[..]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
28Antonio Virdis - 2019
Find Bug-Wally[..]
int iSx = start , iDx = mid;
int stop , iRim;
std::vector<int> tempResult;
while(1)
{if(arr[iSx] < arr[iDx]);
{tempResult.push_back(arr[iSx++]);
if(iSx == mid)
{ iRim = iDx;
stop = end;
break;}
continue;
}if(arr[iSx] >= arr[iDx])
{tempResult.push_back(arr[iDx++]);
if(iDx == end+1)
{ iRim = iSx;
stop = mid;
break;
}
[..]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
29Antonio Virdis - 2019
Ordinamenti multi-valore
ID
Priorità
ID
Priorità
vs
⚫ Richieste servite in ordine di ID crescente
⚫ A parità di ID, si serve in ordine di priorità decrescente
Richiesta Richiesta
30Antonio Virdis - 2019
Richiesta
struct Richiesta
{
int id_;
int prio_;
// costruttore con lista init
Richiesta(int id, int prio):
id_(id) , prio_(prio){}
};
1
2
3
4
5
6
7
8
9
10
11
31Antonio Virdis - 2019
STL: sort()
sort ( first, last, comparatore );
Estremi del vettore da ordinare Funzione di confronto⚫ True⚫ False
32Antonio Virdis - 2019
Richiestabool confrontaRichieste( Richiesta r1 , Richiesta r2)
{
// SE ID1 < ID2
// VINCE 1
// SE ID1 == ID2
{
// SE PRIO1 > PRIO2
// VINCE 1
}
// TUTTI GLI ALTRI CASI
// VINCE 2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
33Antonio Virdis - 2019
Richiestabool confrontaRichieste( Richiesta r1 , Richiesta r2)
{
if( r1.id_<r2.id_ )
return true;
else if(r1.id_ == r2.id_)
{
if(r1.prio_>r2.prio_)
return true;
}
else
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
?
34Antonio Virdis - 2019
Richiestabool confrontaRichieste( Richiesta r1 , Richiesta r2)
{
if( r1.id_<r2.id_ )
return true;
else if(r1.id_ == r2.id_)
{
if(r1.prio_>r2.prio_)
return true;
else
return false;
}
else
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
35Antonio Virdis - 2019
Tipo Accessi
vs
36Antonio Virdis - 2019
Tipo Accessi
vs
37Antonio Virdis - 2019
liste
head
value next value next value next
38Antonio Virdis - 2019
liste
head tail
value next value next value next
Solo inserimento in coda
39Antonio Virdis - 2019
Lettura su ListaObj * leggiInput()
{
// LEGGO LUNGHEZZA
// VARIABILI DI APPOGGIO
// PER TUTTA LA LUNGHEZZA
{
// LEGGO VALORE
// CREO E INIZIALIZZO OGGETTO
// AGGIORNO TESTA
}
// RITORNO TESTA
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
40Antonio Virdis - 2019
Lettura su ListaObj * leggiInput()
{
int value , l;
cin >> l;
Obj * head , * newObj;
for( int i = 0 ; i < l ; ++i )
{
cin >> value;
newObj = new Obj();
newObj->next_ = head;
newObj->value_ = value;
head = newObj;
}
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
41Antonio Virdis - 2019
Stampa Lista
void stampaLista( Obj * head )
{
Obj * pointer = head;
while( pointer != NULL )
{
cout << pointer->value_ << endl ;
pointer = pointer->next_;
}
cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
42Antonio Virdis - 2019
Birra!
43Antonio Virdis - 2019
Ballmer's Peak
Fonte: https://xkcd.com/323/
Hello world
Segmentation fault
Antonio Virdis - 2019
Antonio Virdis - 2019
46Antonio Virdis - 2019
Valgrind
⚫ Babysitter Memoria
⚫ Controlla accessi
⚫ Conta accessi
valgrind ./eseguibile
Antonio Virdis - 2019
g++ -g -o eseguibile eseguibile.cpp
valgrind ./eseguibile
Antonio Virdis - 2019
Antonio Virdis - 2019
Stampa Lista
void stampaLista( Obj * head )
{
Obj * pointer = head;
while( pointer != NULL )
{
cout << pointer->value_ << endl ;
pointer = pointer->next_;
}
cout << endl;
}
18
19
20
21
22
23
24
25
26
27
28
29
File testList.cpp
Antonio Virdis - 2019
Lettura su ListaObj * leggiInput()
{
int value , l;
cin >> l;
Obj * head , * newObj;
for( int i = 0 ; i < l ; ++i )
{
cin >> value;
newObj = new Obj();
newObj->next_ = head;
newObj->value_ = value;
head = newObj;
}
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
51Antonio Virdis - 2019
Operazioni su Lista
⚫ Ricerco un elemento e lo sposto in testa
⚫ Scorrere
⚫ Estrazione
⚫ Inserzione testa
⚫ Ricerco un elemento e lo sposto in coda
⚫ Scorrere
⚫ Estrazione
⚫ Inserimento in coda...
52Antonio Virdis - 2019
Merge Sort Ibrido
Size
Size/2 Size/2
Size/4 Size/4 Size/4 Size/4
53
ESERCIZI:
Antonio Virdis - 2019
54Antonio Virdis - 2019
Distinti in Array
1 7 9 1 1 9
⚫ Input:
⚫ Output:
elementi array
array senza duplicati
55Antonio Virdis - 2019
K interi più frequenti
1 7 9 1 1 9
⚫ Input:
⚫ Output:
elementi array , intero k
primi k valori più frequenti
3
56Antonio Virdis - 2019
K interi più grandi
1 6 9 3 2 8
⚫ Input:
⚫ Output:
elementi array , intero k
primi k valori ordinati in maniera decrescente
K=2
57Antonio Virdis - 2019
Somma Massima
3 7 -8 -5 1 10 1 -3
10
⚫ Input: array
⚫ Output: somma massima
⚫ Esempio 3 7 -8 -5 1 10 1 -3
12
58Antonio Virdis - 2019
Soluzione 1int somme1(int a[] , int size )
{
for(i=0; i<size; i++) // n
{
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
59Antonio Virdis - 2019
Soluzione 1int somme1(int a[] , int size )
{
for(i=0; i<size; i++) // n
{
for(j=i; j<size; j++) // n
{
}
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
60Antonio Virdis - 2019
Soluzione 1int somme1(int a[] , int size )
{
int somma;
int i,j,k;
int max=a[0];
for(i=0; i<size; i++) // n
{
for(j=i; j<size; j++) // n
{
somma=0;
for(k=i; k<=j; k++) // n
{
somma+=a[k];
}
if(somma > max) max=somma;
}
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
61Antonio Virdis - 2019
Soluzione 1int somme1(int a[] , int size )
{
int somma;
int i,j,k;
int max=a[0];
for(i=0; i<size; i++) // n
{
for(j=i; j<size; j++) // n
{
somma=0;
for(k=i; k<=j; k++) // n
{
somma+=a[k];
}
if(somma > max) max=somma;
}
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
( )3
n
62Antonio Virdis - 2019
Soluzione 2int somme2(int a[] , int size )
{
int somma;
int i,j;
int max=a[0];
for(i=0; i<size; i++)
{
somma=0;
for(j=i; j<size; j++)
{
somma+=a[j];
if(somma > max) max=somma;
}
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
63Antonio Virdis - 2019
Soluzione 2int somme2(int a[] , int size )
{
int somma;
int i,j;
int max=a[0];
for(i=0; i<size; i++) // n
{
somma=0;
for(j=i; j<size; j++) // n
{
somma+=a[j];
if(somma > max) max=somma;
}
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
( )2
n
64Antonio Virdis - 2019
Esercizi
⚫ Esperimenti
⚫ Merge vs Insertion sort vs Ibrido
⚫ Soluzioni array somma massima
⚫ Input critici (array inverso, array ordinato)
⚫ Esercizi
⚫ Inserimenti testa/coda liste
⚫ Distinti
⚫ Più frequenti
⚫ Più grandi