1

Parte 10

Elementi di Informatica di baseDott.ssa Elisa Tiezzi

2

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.

3

QUICKSORTAlgoritmo:• 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/xA e x< A[h]}A2={x/xA 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.

4

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.

5

• 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.

6

POSIZIONI

1 2 3 4 5 6 7 8 9 10

30 40 25 50 15 45 38 5 10 35

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

I colori giallo e verde indicano rispettivamente i cursori p e q

Evoluzione dell’array A durante le partizioni intorno al perno

7

Codice per Quicksortpublic 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;

8

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;}

9

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.

10

Relazione di ricorrenza per il Quicksort

C(n) 0 n 0,1

C(n) P(n) C(q 1) C(n q)

q indica la posizione del perno

Complessità di perno

Complessità su A1

Complessità su A2

11

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)

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:

12

Caso medio per QuicksortDato 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

CM (n) n 1 1n

(CM ( j 1) CM (n j))j1

n

13

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 :

CM (n) 2(n 1)1

kk 3

n1 2(n 1)(log(n 1) log2)

Quindi CM (n) O(nlogn)

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,

14

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.

15

Caso pessimo QuicksortIn 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

j (n 2)(n 1)

2 3 O(n2

j3

n1 )

16

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.

17

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.

18

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.

19

Codice per Mergesortpublic 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)

}

20

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];}

21

C(1) 0

C(n) 2C(n2) M(n)

M(n) n nel caso pessimo

C(n) O(nlogn)

Numero di confronti richiesto dal Merge

Studio della complessità per il Mergesort

22

Mergesort è un algoritmo ottimo anche nel caso pessimo: il motivo è ancora da ricercarsi nel fatto che la partizione operata da Mergesort è sempre bilanciata!