Parte 10
Elementi di Informatica di base
Dott.ssa Elisa Tiezzi
1
Algoritmi di ordinamento
Problema: Sia A un array di n elementi tra i quali é definita
una relazione di ordine totale <. Si vuole permutare tali
elementi in maniera tale che risulti :
A[1]< A[2]<……< A[n]
Dove con A[i] indichiamo il valore dell’ennesimo elemento
dell’array.A.
2
QUICKSORT
Algoritmo:
• si sceglie a caso un elemento detto perno A[h].
• si confronta con A[h] tutti gli altri elementi di A e si
costruiscono due insiemi A1 e A2 tali che:
A1={x/xA e x< A[h]}
A2={x/xA e x> A[h]}
• si trasferiscono gli elementi di A1 all’inizio dell’array, seguiti dal
perno, seguiti dagli elementi di A2.
•Si ripete ricorsivamente quicksort.
3
Esempio:
A[1]=30 A[2]=40 A[3]=25 A[4]=50 A[5]=15 A[6]=45 A[7]=38
A[8]=5 A[9]=10 A[10]=35.
• Se la distribuzione iniziale è casuale posso scegliere come perno
anche A[1].
• Si scorrerà l’array A dal secondo elemento con due cursori p e q:
p punterà inizialmente ad A[2] e si sposterà verso destra; q punterà
ad A[n] ( nell’esempio A[10]) e si sposterà verso sinistra.
• Il movimento dei cursori si arresta non appena:
A[1]<A[p] e A[1]> A[q]
• A questo punto si scambiano di posto A[p] e A[q] e si riprende il
moto dei cursori, iterando il procedimento finché i cursori si
incontrano in posizione intermedia.
4
• Si scambia allora di posto A[1] con l’elemento minore più a
destra ottenendo così una permutazione di A in cui si trovano
all’inizio gli elementi minori del perno, quindi il perno e infine
tutti gli elementi maggiori del perno.
• I sottoinsiemi:
A1={15, 10, 25, 5}
A2={45,38,50,40,35}
Saranno trattati ricorsivamente nello stesso modo.
5
Evoluzione dell’array A durante le partizioni intorno al perno
30
40
25
50
POSIZIONI
5
6
15
45
30
10
25
50
15
45
38
5
40
35
30
10
25
5
15
45
38
50
40
35
15
10
25
5
30
45
38
50
40
35
1
2
3
4
7
8
9
10
38
5
10
35
I colori giallo e verde indicano rispettivamente i cursori p e q
6
Codice per Quicksort
public static void quicksort(int[] A)
{ quicksort (A,0,A.lenght-1);}
public static void quicksort(int[] A, int i, int j)
{
if (i >=j)return;
int p= perno(A,i,j);
if (i <(p-1)) quicksort(A,i,p-1);
if ((p+1)<j) quicksort(A,p+1,j);
}
public static int perno(int[] A, int i, int j)
{
int p=i+1;
int q=j;
7
while ((p<q) && (p<=j))
{
while ((p<=j) && (A[i]>=A[p])) p++;
while (A[i]<A[q]) q--;
if (p<q)
{
int temp;
temp=A[p];
A[p]=A[q];
A[q]=temp;
p++;
q--;
}
}
int temp;
temp=A[i];
A[i]=A[q];
A[q]=temp;
return q;
}
8
L’algoritmo, scritto qui con sintassi java, ha un metodo
perno non ricorsivo. E’ chiamato su un array di interi A
partiziona le parti comprese tra i e j attorno al perno
generico A[i]. I due cursori sono p e q e partono appunto
dalle posizioni i+1 e j (nell’esempio A[2] e A[10]).
Il metodo perno restituisce la posizione del perno. Il
metodo quicksort(A,i,j) richiama perno
ricorsivamente provocando l’ordinamento dell’array tra i e j.
Il metodo quicksort(A) provoca l’ordinamento
dell’intero array.
9
Relazione di ricorrenza per il Quicksort
C(n)  0 n  0,1
C(n)  P(n)  C(q 1)  C(n  q)

Complessità
di perno

Complessità
su A1

Complessità
su A2
q indica la posizione del perno
10
Analizzando il metodo perno ci accorgiamo che il ciclo
esterno si ferma quando p>q cioè p=q+1 cioè
quando A[p] è l’elemento più a sinistra maggiore del perno
e A[q] è l’elemento più a destra minore del perno. Ciò
significa che tutti gli elementi (n-1 elementi se non contiamo il
perno) vengono confrontati 1 volta sola con il perno tranne
A[p] e A[q] che sono in genere confrontati 2 volte con li
perno. Abbiamo quindi:
P(n)  (n  3)  4  n 1
quindi la relazione diventa :
C(n)  0 n  0,1
C(n)  n  1  C(q 1)  C(n  q)
11
Caso medio per Quicksort
Dato che il valore j prodotto dal metodo perno può essere con
la stessa probabilità 1/n in ciascuna posizione tra 1 e n
abbiamo per il caso medio:
CM (n)  0
n  0,1
1 n
CM (n)  n  1   (CM ( j  1)  CM (n  j))
n j 1
12
Tale relazione dopo una serie di calcoli che saranno svolti a
lezione e che potete trovare nel libro “Algoritmi e strutture
dati” di Fabrizio Luccio diventa la seguente funzione esplicita
in n :
1
CM (n)  2(n 1)   2(n  1)(log(n 1)  log2)
k 3 k
Quindi CM (n) O(nlogn)
n1
L’algoritmo quindi stabilisce una relazione di ordinamento tra
moltissime coppie senza confrontarle direttamente ma inferendo
tale relazione da confronti fatti con altri elementi.
Infatti se si eseguissero tutti i possibili confronti tra coppie di
elementi si avrebbe CM(n)=n(n-1)/2 cioè quante sono le coppie
distinte di n elementi,
13
Il comportamento medio di tale algoritmo si avvantaggia del
fatto che le successive partizioni di dati sono mediamente
bilanciate. Supponiamo infatti che l’elemento perno abbia il
valore centrale di A. Il metodo perno mette il perno al centro e
costruisce i due insiemi A1 e A2 di dimensione metà
dell’insieme originale: il metodo corre perfettamente secondo
partizioni bilanciate dell’insieme. Si eseguono n+1 confronti
per tutte le chiamate di perno ad ogni livello di ricorrenza, ma
tali livelli sono meno quando le successive partizioni
dell’insieme sono perfettamente bilanciate! Ecco che nel caso
ottimo il perno ha il valore centrale e C(n) é dell’ordine
nlogn.
14
Caso pessimo Quicksort
In questo caso il perno è sull’elemento che risulta il minimo ( o il
massimo) degli elementi di A.
In questo caso si ha che A1 è vuoto mentre A2 contiene n-1 elementi.
Abbiamo quindi:
C(n)  n  1  C(n  1) 
 (n  1)  (n)  C(n  2) 
 (n  1)  (n)  (n  1)  C(n  3) 
 ......................... 
 (n  1)  n  (n  1)  (n  2)  ..  3 
n 1
(n  2)(n  1)
  j
 3 O(n 2 )
j 3
2
15
Nel caso pessimo quindi il numero dei confronti ha un numero assai
maggiore che nel caso medio, questo dipende dal completo
sbilanciamento della partizione di A, che obbliga essenzialmente ad
eseguire tutti i possibili confronti tra coppie di elementi.
Da osservare che Quicksort opera con massima inefficienza quando
l’insieme è già ordinato.
16
MERGESORT
Non abbiamo comunque individuato un metodo di ordinamento
che operi O(nlogn) confronti anche nel caso pessimo (il limite
inferiore al numero di confronti generato con l’albero di
decisione è O(nlogn) sia nel caso medio che nel caso pessimo);
la possibilità di raggiungere questo risultato appare legato alla
costruzione di un algoritmo che lavori su partizione dell’insieme
bilanciate in ogni caso: il Mergesort.
17
Il Mergesort , chiamato anche metodo di ordinamento per
fusione, si basa sull’idea di dividere l’insieme da ordinare A (o
meglio l’array nel nostro codice) di n elementi in due sottoinsiemi
di n/2 elementi ciascuno, ordinare poi ciascuna sequenza e
fondere insieme le due unità ordinate in un’unica sequenza. In
realtà nella versione ricorsiva qui presentata Mergesort si applica
all’intero array e ne costruisce l’ordinamento mediante la fusione
di due semi-insiemi ordinati ricorsivamente nello stesso modo.
Nel Mergesort le chiamate ricorsive si susseguono l’una dentro
l’altra finchè si raggiungono insiemi elementari di due elementi
su cui iniziare le vere e proprie operazioni di confronto e
ordinamento, con la fusione di due sottoinsiemi di un elemento
ciascuno (procedura Merge non ricorsiva). Da qui si passa via via
alla fusione di sottoinsiemi più grandi: le operazioni iniziano
sempre su dati elementari.
18
Codice per Mergesort
public static void mergesort(int[] A)
{ aus=new int[A.lenght]
mergesort(A,0,A.lenght-1);}
public static void mergesort(int[] A, int i, int j)
{
if (i >=j)return;
int m= (i+j)/2;
mergesort(A,i,m);
mergesort(A,m+1,j);
merge(A,i,j,m)
}
19
public static void merge(int[] A, int i, int j,int m)
{
int p=i;
int q=m+1;
int k=i;
while ((p<=m) && (q<=j))
{ if (A[p]<A[q]) {aus[k]=A[p]; p++; }
else {aus[k]=A[q]; q++; }
k++; }
if (p<=m)
{p=m;
for(int k1=j;k1>=k;k1--)
{A[k1]=A[p];p--;}}
for(int k1=i;k1<k;k1++)
{A[k1]=aus[k];
}
20
Studio della complessità per il Mergesort
C(1)  0
C(n)  2C( n 2 )  M(n)

Numero di confronti
richiesto dal Merge
M(n)  n nel caso pessimo
C(n) O(nlogn)
21
Mergesort è un algoritmo ottimo anche nel caso pessimo: il
motivo è ancora da ricercarsi nel fatto che la partizione operata da
Mergesort è sempre bilanciata!
22