Università degli Studi di Cagliari
Corso di Laurea Specialistica in Ingegneria per l’Ambiente ed il Territorio
Corso di Laurea Specialistica in Ingegneria Civile - Strutture
FONDAMENTI DI
INFORMATICA 2
http://www.diee.unica.it/giacinto/FI2
ALGORITMI DI ORDINAMENTO
E RICERCA BINARIA
Docente: Giorgio Giacinto
AA 2008/2009
Introduzione
!
!
!
!
Gli algoritmi di ordinamento vengono utilizzati
in moltissime applicazioni
Esistono diversi algoritmi che risolvono il
problema dell’ordinamento in modi diversi
Ciascun algoritmo è caratterizzato da una
diversa efficienza
In questo modulo verranno presentati i
principali algoritmi e una valutazione
qualitativa dell’efficienza
Giorgio Giacinto 2008
Fondamenti di Informatica II
2
Il problema dell’ordinamento
!
!
Si supponga di avere una lista di dati per i quali sia
definita una relazione di ordinamento.
Si vuole modificare la sequenza degli elementi della
lista in modo che siano ordinati in senso crescente
Sugli elementi della lista deve essere definita una
relazione di ordinamento.
!
Ad es. può essere una lista di numeri (interi o frazionari),
una lista di parole, una lista di strutture che può essere
ordinata rispetto a uno o più campi (elenco studenti può
essere ordinato per cognome, per voto, ecc.)
Giorgio Giacinto 2008
Fondamenti di Informatica II
3
Il problema dell’ordinamento
(cont.)
!
!
Per semplicità si farà riferimento al problema
dell’ordinamento in senso crescente di una lista
di N interi rappresentata mediante un array.
int A[N];
Con le opportune modifiche gli algoritmi possono
essere utilizzati
!
!
per ordinare liste rappresentate in modo differente (ad
es. con puntatori)
per ordinare elementi complessi (ad es. rappresentati
con strutture, da ordinare rispetto a uno dei campi)
Giorgio Giacinto 2008
Fondamenti di Informatica II
4
Algoritmi di ordinamento
!
!
!
!
!
SelectionSort
BubbleSort
MergeSort
QuickSort
Gli algoritmi sono in ordine di efficienza
crescente e di intuitività decrescente.
Giorgio Giacinto 2008
Fondamenti di Informatica II
5
Selection Sort
!
Idea
l’array è ordinato se A[i] ! A[j] per ogni i, 0 ! i < N-1, e
per ogni j, i+1 ! j <N
!
!
Due fasi
Cerca (“seleziona”) l’elemento più piccolo nell’array
e scambialo con il primo elemento dell’array
Ripeti il passo (1) sull’array ottenuto escludendo il
primo elemento. Se l’array è vuoto, hai finito
Giorgio Giacinto 2008
Fondamenti di Informatica II
6
Selection Sort – versione
iterativa
!
Ad ogni iterazione i l’array da 0 a i – 1 è ordinato,
mentre la parte di array da i a N-1 contiene elementi
dell’array maggiori di quelli contenuti da 0 a i –1, e
deve essere ancora ordinato.
ordinato
0
!
non ordinato
i -1 i
N-1
Due iterazioni annidate
!
!
Una più esterna che scandisce tutto l’array
Una più interna che cerca l’elemento più piccolo nella parte
di array successiva all’elemento individuato dalla iterazione
esterna
Giorgio Giacinto 2008
Fondamenti di Informatica II
7
Selection Sort – versione
iterativa
void SelectionSort(int* A, int n)
{
int i, j, small, temp;
for (i = 0; i < n-1; i++) {
/*Cerca il minimo*/
small = i;
for (j = i+1; j < n; j++)
if (A[j] < A[small])
small = j;
temp = A[small];
/*scambia l’elemento di */
A[small] = A[i];
/*indice small con quello*/
A[i] = temp;
/*di indice i
*/
}
}
Giorgio Giacinto 2008
Fondamenti di Informatica II
8
BubbleSort
!
!
!
Idea l’array è ordinato se per ogni i, 0 ! i < N-1, A[i] ! A[i+1]
Algoritmo:
Per ogni 0 ! i < N-1
Scandisci l’array partendo ”dal basso” (j = N-1) fino a j = i+1.
Se A[j] < A[j-1] scambia i due elementi
L’elemento più piccolo “sale” nel vettore fino a
trovare la sua posizione, come se fosse una bolla
! Al
termine della i-esima iterazione l’array è ordinato dalla
posizione 0 alla posizione di indice i.
! Se alla i-esima iterazione non è stato fatto nessuno
scambio, tutto l‘array è ordinato!
Giorgio Giacinto 2008
Fondamenti di Informatica II
9
Esempio
1 iterazione: i = 0
2 iterazione: i = 1
38
38
38
63
63
25
41
25
25
(a)
j
25
25
38
38
63
63
41
41
41
41
(b)
(c)
(d)
j
(a) Scambio 25 con 41
(b) Scambio 25 con 63
(c) Scambio 25 con 38
Giorgio Giacinto 2008
j
j
63
(e)
(d) Scambio 41 con 63
(e) Ordinamento terminato
Fondamenti di Informatica II
10
BubbleSort
void BubbleSort(int *A,int n){
int i,another,temp;
for(i=0;i<n-1;i++)
{
another=0;
for (j=n-1;j>i;j--)
if ((A[j] < A[j-1]))
{
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
another=1;
}
if(!another) break;
}
Giorgio Giacinto 2008
Fondamenti di Informatica II
11
Confronto Selection Sort –
BubbleSort
!
!
Selection Sort esegue sempre lo stesso
numero di operazioni
BubbleSort invece esegue un numero di
operazioni variabili a seconda
dell’ordinamento già presente nel vettore
!
!
Caso migliore: l’array è già ordinato ed è
sufficiente effettuare solo un ciclo per verificare
che tutti gli elementi sono ordinati
Caso peggiore: gli elementi nell’array sono
ordinati in senso decrescente
Giorgio Giacinto 2008
Fondamenti di Informatica II
12
MergeSort
!
E’ formulato ricorsivamente (divide et impera)
BASE
Se l’array ha due elementi, scambia gli
elementi se non sono ordinati
INDUZIONE
Se l’array ha più di due elementi lo si divide a
metà e si ordinano i due array ottenuti
usando lo stesso metodo. I due array
vengono quindi fusi per formare l’array
completo
Giorgio Giacinto 2008
Fondamenti di Informatica II
13
Esempio: fusione di due array
ordinati
A
2
A
i
C
2
6
2
h
6
A
C
i
2
3
6
h
9
9
10
10
10
B
B
B
3
k
3
k
2
3
4
h
3
4
4
5
5
5
8
8
8
Fondamenti di Informatica II
i
9
4
Giorgio Giacinto 2008
C
2
k
ecc.
14
Fusione (merge) di due array
ordinati
!
Dati due array A e B con m componenti ordinate in
ordine crescente, si vuole ottenere un unico array
C ordinato costituito dai 2m elementi di A e B.
1.
2.
3.
4.
Sia i l’indice per scandire A, k l’indice per scandire B e h
l’indice che usiamo per costruire l’array C
Inizializziamo k=0, i=0, h=0
Se A[i]<B[k] allora C[h++]=A[i++];
altrimenti C[h++]=B[k++];
Ripetere il passo 3 finchè uno dei due array (o entrambi)
non è esaurito.
Inserire gli elementi dell’array non ancora esaurito nelle
posizioni restanti di C
Giorgio Giacinto 2008
Fondamenti di Informatica II
15
Funzione “merge”
merge (int* A, int left, int mid, int right)
{
int i=left, k=mid+1, h=0;
int j;
int temp[N_MAX];
}
while ((i <= mid) && (k <= right))
if(A[i] <= A[k]) temp[h++] = A[i++];
else temp[h++] = A[k++];
if (i == mid+1) {
for (j = k; j <= right; j++)
temp[h++] = A[j];
} else {
for (j = i; j <= mid; j++)
temp[h++] = A[j];
}
for (j = 0; j <= right-left; j++)
A[j+left] = temp[j];
Giorgio Giacinto 2008
Fondamenti di Informatica II
16
Funzione “merge”
!
Nel caso di “MergeSort” la funzione “merge” deve
fondere due parti contigue di uno stesso array
!
Ad esempio la parte fra left e right viene divisa a metà, con
mid il punto centrale. Le parti da left a mid e da mid+1 a
right vengono ordinate separatamente e poi fuse insieme.
Al termine la parte fra left e right conterrà gli elementi
ordinati.
left
!
mid right
La funzione precedente effettua la fusione fra due metà
ordinate delimitate da left e mid, e da mid+1 a right
Giorgio Giacinto 2008
Fondamenti di Informatica II
17
Commenti sulla funzione
merge
!
!
La funzione merge contiene anche il passo base
della ricorsione:
un vettore di due elementi corrisponde al caso in cui
left = mid e right = mid+1, che vengono scambiate
se non sono in ordine.
L’algoritmo completo MergeSort:
!
!
divide ripetutamente il vettore a metà, finché si generano
segmenti contenenti uno o due componenti.
Ciascun segmento viene ordinato e si effettua la fusione fra
i segmenti in sequenza inversa rispetto alla fase di
divisione
Giorgio Giacinto 2008
Fondamenti di Informatica II
18
Mergesort
void mergeSort(int* A, int n)
{
mSort(A,0,n-1);
}
void mSort(int* A, int left, int right)
{
int mid;
if (left < right) {
mid = (right + left)/2;
mSort(A, left, mid);
mSort(A, mid+1, right);
merge(A, left, mid, right);
}
}
Giorgio Giacinto 2008
Fondamenti di Informatica II
19
Esempio: MergeSort
Ordinare {23 5 7 9 45 21 2 75} con 8 elementi
!
!
!
Mergesort attiva mSort(0,7) che attiva mSort(0,3) che attiva
mSort(0,1).
mSort(0,1) scambia i primi due elementi
il controllo torna a mSort(0,3) che chiama mSort(2,3)
mSort(2,3) non effettua modifiche: gli elementi sono già ordinati
il controllo torna a mSort (0,3) che effettua la fusione fra i due array:
{5 7 9 23 45 21 2 75)
Il controllo torna alla chiamata a mSort(0,7), che attiva mSort(4,7),
che attiva mSort(4,5) e mSort(6,7)… fino a ottenere l’array ordinato
Giorgio Giacinto 2008
Fondamenti di Informatica II
20
Esempio: attivazioni di
MergeSort
mSort(0,7)
mSort(4,7)
mSort(0,3)
mSort(0,1)
Giorgio Giacinto 2008
mSort(2,3)
mSort(4,5)
mSort(6,7)
Fondamenti di Informatica II
21
Valutazione efficienza di
MergeSort
!
!
Mergesort è teoricamente più efficiente dei primi due
algoritmi, se si trascura il “costo” della ricorsione.
Tuttavia non sempre il “costo” della ricorsione è
trascurabile, soprattutto se l’array ha piccole
dimensioni
!
!
L’efficienza aumenta se si formula l’algoritmo non
ricorsivamente
In generale MergeSort può essere più efficiente
degli altri algoritmi in caso di dimensioni elevate
dell’array
Giorgio Giacinto 2008
Fondamenti di Informatica II
22
Ordinamento veloce
(QuickSort)
!
E’ uno degli algoritmi più utilizzati perché
risulta essere uno dei più efficienti
sperimentalmente
! Non
!
lo è invece dal punto di vista teorico!
Spesso viene fornito come funzione di libreria
dai compilatori
Giorgio Giacinto 2008
Fondamenti di Informatica II
23
QuickSort
IDEA
Scegliere un elemento dell’array, chiamato pivot, e
dividere l’array in due:
!
!
uno contenente solo elementi minori dell’elemento pivot
l’altro contenente solo elementi maggiori o uguali
all’elemento pivot
La procedura si applica ricorsivamente alle due parti
fino a ottenere array di dimensione unitaria: a
questo punto l’array di partenza è ordinato!
Giorgio Giacinto 2008
Fondamenti di Informatica II
24
QuickSort: partizionamento
1.
2.
Scegli a caso un elemento dell’array come pivot (ad es.
il primo elemento)
Due indici, i e j, scandiscono l’array
"
"
j parte dalla fine e si ferma quando trova un elemento minore o
uguale dell’elemento pivot
i parte dall’inizio e si ferma quando trova un elemento maggiore
o uguale dell’elemento pivot o finché non raggiunge l’altro
indice
Se i < j, i due elementi individuati da i e j vengono scambiati e
prosegue la scansione dell’array da parte dei due indici.
Quando i due indici si incontrano, l’array è diviso in due
parti tali che a sinistra si trovano solo elementi minori
del pivot, mentre a destra solo elementi maggiori del
pivot.
Giorgio Giacinto 2008
Fondamenti di Informatica II
25
QuickSort: esempio di
partizionamento
Tutti gli elementi da 0 a j sono
inferiori agli elementi della
parte restante.
20
20
40
40
40
10
10
10
62
62
25
25
25
j
70
70
70
i
13
13
60
20
i
j
Giorgio Giacinto 2008
60
i
j
13
62
60
Uso la stessa tecnica su
ciascuna delle due parti
separatamente, e così via.
Termino quando una
successiva suddivisione
genera parti che contengono
un solo elemento: l’array
risulta ordinato!
Fondamenti di Informatica II
26
QuickSort - partition
int partition (int* A, int l, int r)
{
int pivot = A[l], i=l-1, j=r+1;
int temp;
for (; ;) {
do j--; while (A[j]>pivot);
do i++; while (A[i]<pivot);
if (i<j) {
temp=A[i];
A[i]=A[j];
A[j]=temp;
} else
return j;
}
}
Giorgio Giacinto 2008
Fondamenti di Informatica II
27
QuickSort - qsort
int qSort(int* A, int left, int right)
{
int q;
if (left < right) {
q = partition(A,left,right);
qSort(A, left, q);
qSort(A, q+1, right);
}
}
void quickSort(int* A, int n)
{
qSort(A,0,n-1);
}
Giorgio Giacinto 2008
Fondamenti di Informatica II
28
Esempio: attivazioni di
QuickSort
qSort(0,7)
qSort(5,7)
qSort(0,4)
qSort(0,1)
qSort(2,4)
qSort(5,6)
qSort(2,3)
Giorgio Giacinto 2008
Fondamenti di Informatica II
29
Ricerca di un elemento in un
array ordinato
int bin_search(int key, int* A, int n)
{
int left=0, right=n-1;
while (left<=right) {
int mid=(left+right)/2;
if (A[mid]==key)
return mid;
if (A[mid]>key)
right=mid-1;
else
left=mid+1;
}
return -1; /* Elemento non trovato */
}
Giorgio Giacinto 2008
Fondamenti di Informatica II
30