Laboratorio di Algoritmi e Strutture Dati Ingegneria e...

Algoritmi di ordinamento: MergeSortAlgoritmi di ordinamento: QuickSort

Laboratorio di Algoritmi e Strutture DatiIngegneria e Scienze Informatiche - Cesena

A.A. 2013-2014

Pietro Di Lena

[email protected], [email protected]

Pietro Di Lena Laboratorio di Algoritmi e Strutture Dati


Merge Sort

Merge Sort

Algoritmo di ordinamento ricorsivo basato sulla tecnica Divide Et Impera.

Ideato da Jon Von Neumann nel 1945

Costo computazionale:Caso pessimo: Θ(n log n)Caso medio: Θ(n log n)Caso ottimo: Θ(n log n)

Algoritmo non in place: richiede O(n) di memoria ausiliaria.

Implementato come algoritmo di ordinamento standard (con alcuneottimizzazioni) nelle librerie di alcuni linguaggi (Perl, Java) e alcuneversioni di Linux.



Merge Sort

MergeSort: pseudocodice

1: procedure MergeSort(A, p, r)2: if p < r then3: q ← (p + r)/24: MergeSort(A, p, q)5: MergeSort(A, q + 1, r)6: Merge(A, p, q, r)7: end if8: end procedure

1: procedure Merge(A, p, q, r)2: i ← p, j ← q + 1, k ← 03: while i ≤ q and j ≤ r do4: if A[i ] ≤ A[j] then5: B[k]← A[i ]6: i ← i + 17: else8: B[k]← A[j]9: j ← j + 1

10: end if11: k ← k + 112: end while13: while i ≤ q do14: B[k]← A[i ]15: i ← i + 116: k ← k + 117: end while18: while j ≤ r do19: B[k]← A[j]20: j ← j + 121: k ← k + 122: end while23: for k ← p to r do24: A[k]← B[k − p]25: end for26: end procedure



Merge Sort

Nota: come generare una lista di numeri random

#include <stdio.h>#include <stdlib.h>#include <time.h>

int main(int argc , char *argv []) {int i, max , size;if(argc !=3) {fprintf(stderr ,"Usage: randlist <maxint > <size >\n");return 1;

}max=atoi(argv [1]);size=atoi(argv [2]);

/* Inizializza il seed del generatore di numeri casualiutilizzando l’orologio di sistema.

*/srand(time(NULL));

for(i=0; i<size; i++) printf ("%d ",rand()%(max+1));printf ("\n");return 0;

}



Merge Sort

Nota: come calcolare il tempo di CPU in un programma C

#include <stdio.h>#include <stdlib.h>#include <time.h>

int main(int argc , char *argv []) {clock_t start ,end;

start=clock ();// Codice della proceduraend=clock();

printf ("Time: %f sec\n",(double)(end -start)/CLOCKS_PER_SEC);

return 0;}



QuickSortOttimizzazioni per il QuickSortQuicksort nella libreria standard C

QuickSort

Algoritmo di ordinamento ricorsivo basato sulla tecnica Divide Et Impera.

Ideato da Tony Hoare nel 1960, in visita come studente presso la MoscowState University.

Oggetto della tesi si dottorato di Robert Sedgewick nel 1975.

Implementato come algoritmo di ordinamento standard nella libreria C diUnix (qsort()).

Costo computazionale:Costo pessimo: Θ(n2)Caso medio: Θ(n log n)Caso ottimo: Θ(n log n)

A differenza del MergeSort, il QuickSort non utilizza memoria ausiliaria(algoritmo in place).




QuickSort: pseudocodice

1: procedure QuickSort(A, p, r)2: if p < r then3: q ← Pivot(A, p, r)4: i ← Partition(A, p, q, r)5: QuickSort(A, p, i)6: QuickSort(A, i + 1, r)7: end if8: end procedure

1: function Pivot(A, p, r)2: return random number in [p, .., r ]3: end function

1: procedure Swap(A, i, j)2: tmp ← A[i ]3: A[i ]← A[j]4: A[j]← tmp5: end procedure

1: function Partition(A, p, q, r)2: i ← p3: j ← r4: Swap(A, q, p)5: pivot ← A[p]6: while i < j do7: while j > p and pivot ≤ A[j]

do8: j ← j − 19: end while

10: while i < r and pivot > A[i ] do11: i ← i + 112: end while13: if i < j then14: Swap(A, i, j)15: end if16: end while17: Swap(A,p,j)18: return j19: end function

Come generiamo in C un intero random tra p e r?

Soluzione: p + rand()%(r − p + 1).




Ottimizzazioni per il QuickSort: scelta del pivot

Problema: mantenere le partizioni bilanciate

Soluzione standard: scelta random del pivot

Soluzione ottimizzata: metodo della mediana di 3. Scegliamo il medianotra tre valori distinti.

Scelte possibili per i tre valori:1 Tre posizioni scelte in maniera casuale2 Primo, medio e ultimo valore nel vettore (soluzione proposta sotto)

1: function Pivot(A, p, r)2: q ← (p + r)/23: if A[p] ≤ A[q] ≤ A[r ] or A[r ] ≤ A[q] ≤ A[p] then4: return q5: else if A[q] ≤ A[p] ≤ A[r ] or A[r ] ≤ A[p] ≤ A[q] then6: return p7: else8: return r9: end if

10: end function




Ottimizzazioni per il QuickSort: scelta del pivot

Problema: mantenere le partizioni bilanciate

Soluzione standard: scelta random del pivot

Soluzione ottimizzata: metodo della mediana di 3. Scegliamo il medianotra tre valori distinti. Scelte possibili per i tre valori:

1 Tre posizioni scelte in maniera casuale2 Primo, medio e ultimo valore nel vettore (soluzione proposta sotto)

1: function Pivot(A, p, r)2: q ← (p + r)/23: if A[p] ≤ A[q] ≤ A[r ] or A[r ] ≤ A[q] ≤ A[p] then4: return q5: else if A[q] ≤ A[p] ≤ A[r ] or A[r ] ≤ A[p] ≤ A[q] then6: return p7: else8: return r9: end if

10: end function




Ottimizzazioni per il QuickSort: elementi ripetuti

Problema: le prestazioni dell’algoritmo sono pessime su vettori checontengono molti elementi ripetuti. Provare a lanciare quicksort con unalista di 100000 elementi con valori compresi tra 0 e 5.

Soluzione: metodo three way partition. Partizioniamo l’array in tre sezionidistinte: a sinistra tutti i valori strettamente minori del pivot, al centro ivalori esattamente uguali al pivot, a destra tutti i valori strettamentemaggiori del pivot. Esempio.

Lista in input

3 1 3 5 3 0 0 2 5 4 2 1 2 4 0

Three-Way-Partition con pivot = 2 (mediano tra 3, 2, 0)

0 1 1 0 0 2 2 2 4 5 3 5 4 3 3






Soluzione: metodo three way partition. Partizioniamo l’array in tre sezionidistinte: a sinistra tutti i valori strettamente minori del pivot, al centro ivalori esattamente uguali al pivot, a destra tutti i valori strettamentemaggiori del pivot.

Esempio.

Lista in input

3 1 3 5 3 0 0 2 5 4 2 1 2 4 0


0 1 1 0 0 2 2 2 4 5 3 5 4 3 3






Soluzione: metodo three way partition. Partizioniamo l’array in tre sezionidistinte: a sinistra tutti i valori strettamente minori del pivot, al centro ivalori esattamente uguali al pivot, a destra tutti i valori strettamentemaggiori del pivot. Esempio.

Lista in input

3 1 3 5 3 0 0 2 5 4 2 1 2 4 0


0 1 1 0 0 2 2 2 4 5 3 5 4 3 3




Ottimizzazioni per il QuickSort: three way partition

A[0, .., N], lista di interi, pivot = 2

A[0, .., l − 1] contiene gli elementi strettamente minori del pivot

A[l , .., m − 1] contiene gli elementi uguali al pivot

A[m, .., h], contiene gli elementi non ancora considerati

A[h + 1, .., N], contiene gli elementi strettamente maggiori del pivot

m h↓ ↓3 1 3 5 3 0 0 2 5 4 2 1 2 4 0↑l










m h↓ ↓0 1 3 5 3 0 0 2 5 4 2 1 2 4 3↑l










m h↓ ↓

0 1 3 5 3 0 0 2 5 4 2 1 2 4 3↑l










m h↓ ↓

0 1 4 5 3 0 0 2 5 4 2 1 2 3 3↑l










m h↓ ↓

0 1 2 5 3 0 0 2 5 4 2 1 4 3 3↑l










m h↓ ↓

0 1 2 1 3 0 0 2 5 4 2 5 4 3 3↑l










m h↓ ↓

0 1 1 2 3 0 0 2 5 4 2 5 4 3 3↑l










m h↓ ↓

0 1 1 2 2 0 0 2 5 4 3 5 4 3 3↑l










m h↓ ↓

0 1 1 0 2 2 0 2 5 4 3 5 4 3 3↑l










m h↓ ↓

0 1 1 0 0 2 2 2 5 4 3 5 4 3 3↑l










mh↓

0 1 1 0 0 2 2 2 4 5 3 5 4 3 3↑l










h m↓ ↓

0 1 1 0 0 2 2 2 4 5 3 5 4 3 3↑l










h m↓ ↓

0 1 1 0 0 2 2 2 4 5 3 5 4 3 3↑l

STOP.

Ultimo elemento strettamente minore del pivot puntato da l − 1

Primo elemento strettamente maggiore del pivot puntato da h + 1





1: procedure QuickSort2(A, p, r)2: if p < r then3: q ← Pivot(A, p, r)4: (i, j)← TWP(A, p, q, r)5: QuickSort2(A, p, i)6: QuickSort2(A, j, r)7: end if8: end procedure

1: function TWP(A, p, q, r)2: l ← m ← p3: h ← r4: pivot ← A[q]5: while m ≤ h do6: if A[m] < pivot then7: Swap(A,m,l)8: m ← m + 19: l ← l + 1

10: else if A[m] > pivot then11: Swap(A, m, h)12: h ← h − 113: else14: m ← m + 115: end if16: end while17: return (l − 1, h + 1)18: end function

Costo computazionale di TWP(A, p, q, r) =

Θ(r − q + 1)





1: procedure QuickSort2(A, p, r)2: if p < r then3: q ← Pivot(A, p, r)4: (i, j)← TWP(A, p, q, r)5: QuickSort2(A, p, i)6: QuickSort2(A, j, r)7: end if8: end procedure

1: function TWP(A, p, q, r)2: l ← m ← p3: h ← r4: pivot ← A[q]5: while m ≤ h do6: if A[m] < pivot then7: Swap(A,m,l)8: m ← m + 19: l ← l + 1

10: else if A[m] > pivot then11: Swap(A, m, h)12: h ← h − 113: else14: m ← m + 115: end if16: end while17: return (l − 1, h + 1)18: end function

Costo computazionale di TWP(A, p, q, r) =Θ(r − q + 1)




Ottimizzazioni per il QuickSort: ampiezza dello stack di ricorsione

Problema: partizioni troppo sbilanciate rischiano di generare uno stack diricorsione troppo profondo (l’eseguibile va in segmentation fault).

Soluzione: esistono diverse tecniche per limitare il numero di chiamatericorsive. La tecnica piu semplice consiste nel fermare la ricorsione susotto-array piu piccoli di una dimensione predefinita K . Al termine dellaprocedura ricorsiva abbiamo una lista semi-ordinata che puo essereordinata in una unica passata (velocemente) con l’InsertionSort.

Quanto costa l’InsertionSort su una lista semi-ordinata di n elementi? Perogni elemento della lista dobbiamo eseguire al massimo K confronti,quindi al massimo Kn confronti ⇒ Θ(n) (caso ottimo dell’InsertionSort!).

1: procedure QuickSort2(A, n)2: Sort(A, 0, n − 1)3: InsertionSort(A, n)4: end procedure

1: procedure Sort(A, p, r)2: if p < r then3: q ← Pivot(A, p, r)4: (i, j)← TWP(A, p, q, r)5: if i − p + 1 > K then6: Sort(A, p, i)7: end if8: if r − j + 1 > K then9: Sort(A, j, r)

10: end if11: end if12: end procedure







Quanto costa l’InsertionSort su una lista semi-ordinata di n elementi?

Perogni elemento della lista dobbiamo eseguire al massimo K confronti,quindi al massimo Kn confronti ⇒ Θ(n) (caso ottimo dell’InsertionSort!).










Quanto costa l’InsertionSort su una lista semi-ordinata di n elementi? Perogni elemento della lista dobbiamo eseguire al massimo K confronti,quindi al massimo Kn confronti ⇒ Θ(n) (caso ottimo dell’InsertionSort!).







Quicksort nella libreria standard C

void qsort(void *base, size t nel, size t width, int (*compar)(const void *, const void *));

base: puntatore al primo elemento della lista (convertito ad un puntatore )

nel: numero di elementi nella lista

width: dimensione in byte di ogni elemento nella lista

compar: puntatore ad una funzione che confronta due elementi. Lafunzione deve restituire

un valore minore di zero, se il primo elemento deve essere posizionato primadel secondo nell’ordinamentozero, se i due elementi hanno la stessa posizione nell’ordinamentoun valore maggiore di zero, se il primo elemento deve essere posizionatodopo il secondo nell’ordinamento




Quicksort nella libreria standard C: esempio di utilizzo con liste di interi

#include <stdio.h>#include <stdlib.h>

int *readlist(char *file , int *n) {// Procedura per leggere una lista di interi

}

int int_compare(const void *v1, const void *v2) {return (*( int *)v1 - *(int *)v2);

}

int main(int argc , char *argv []) {int *list ,i,n;

list=readlist(argv [1],&n);qsort(list ,n,sizeof(int),int_compare);

for(i=0; i<n; i++) printf ("%d ",list[i]);printf ("\n");

return 0;}


Laboratorio di Algoritmi e Strutture Dati Ingegneria e...

Documents

Transcript of Laboratorio di Algoritmi e Strutture Dati Ingegneria e...