1

1/232

Algoritmi e Programmazione Avanzata - teoria

2/232

Che cosa c’è nella lezione

Questa lezione si occupa di ordinamenti:

gli algoritmi iterativi di ordinamento

gli algoritmi ricorsivi di ordinamento.

2

3/232

Algoritmi e Programmazione Avanzata - teoria

4/232

Ordinamento internodati in memoria centraleaccesso diretto agli elementi

Ordinamento esternodati in memoria di massaaccesso sequenziale agli elementi

Classificazione: interni/esterni

3

5/232

Ordinamento in locovettore di n dati + locazioni di memoriaausiliarie in numero fisso

Ordinamento stabileimmutato l’ordinamento relativo di elementicon ugual valore della chiave

Classificazione: in loco/stabili

6/232

O(n2):semplici, iterativi, basati sul confronto

Insertion sort, Selection sort, Exchange/Bubble sort

O(n log n):più complessi, ricorsivi, basati sul confrontoMerge sort, Quicksort, Heapsort

O(n):applicabili solo con ipotesi restrittive sui dati, basatisul calcoloCounting sort, Radix sort, Bin/Bucket sort

Classificazione: complessità

4

7/232

Elementi da ordinare: strutture (struct)

Uno dei campi = chiave di ordinamento

Restanti campi = dati aggiuntivi

Ordinamento ascendente/discendente

Ipotesi: vettori di interi di n elementi

Struttura dei dati

8/232

#define N 100struct studente int matricola;

Esempio

5

9/232

#define N 100struct studente int matricola;

Esempio

Ordinamentoper matricola

10/232

#define N 100struct studente int matricola;char cognome[30];char nome[30];

Esempio

Ordinamento per cognome e nome(chiave = concatenazione dicognome e nome)

6

11/232

#define N 100struct studente int matricola;char cognome[30];char nome[30];int voto ;

;

Esempio

Ordinamentoper voto (con valori ripetuti)

12/232

#define N 100struct studente int matricola;char cognome[30];char nome[30];int voto ;

;

struct studente classe[N];

Esempio

7

13/232

Algoritmi basati sul confronto

operazione elementare: confronto ai : aj

esito: decisione (ai>aj o ai≤aj), riportata su unalbero delle decisioni.

Limite inferiore

14/232

Esempio

Ordinare il vettore a1, a2 , a3 di elementi distinti

8

15/232

Esempio

a1 : a2

Ordinare il vettore a1, a2 , a3 di elementi distinti

16/232

Esempio

a2 : a3

a1 : a2

a1 : a3

>≤

Ordinare il vettore a1, a2 , a3 di elementi distinti

9

17/232

Esempio

a2 : a3

a1 : a2

a1 : a3

a1 : a3a1<a2 <a3

>

>

≤

≤

Ordinare il vettore a1, a2 , a3 di elementi distinti

18/232

Esempio

a2 : a3

a1 : a2

a1 : a3

a1 : a3a1<a2 <a3

a1<a3 <a2 a3<a1 <a2

>

>

>

≤

≤

≤

Ordinare il vettore a1, a2 , a3 di elementi distinti

10

19/232

Esempio

a2 : a3

a1 : a2

a1 : a3

a1 : a3a2 : a3a1<a2 <a3

a1<a3 <a2 a3<a1 <a2

a2<a1 <a3

>

>>

>

≤

≤

≤

≤

Ordinare il vettore a1, a2 , a3 di elementi distinti

20/232

Esempio

a2 : a3

a1 : a2

a1 : a3

a1 : a3a2 : a3a1<a2 <a3

a1<a3 <a2 a3<a1 <a2

a2<a1 <a3

a2<a3 <a1 a3<a2 <a1

>

>

>

>

>

≤

≤

≤

≤

≤

Ordinare il vettore a1, a2 , a3 di elementi distinti

11

21/232

Generalizzazione

Per n interi distinti: numero di ordinamenti = numero di permutazioni n!Complessità: numero h di confronti (altezza dell’albero)Ogni soluzione = fogliaNumero di foglie = 2h

Approssimazione di Stirling: n! > (n/e)n

2h ≥ n! > (n/e)n

h ≥ lg(n/e)n = n lg n -n lg e = Ω(n lg n)

22/232

Algoritmi e Programmazione Avanzata - teoria

12

23/232

Dati: interi in un vettore AVettore diviso in 2 sotto-vettori:

di sinistra: ordinatodi destra: disordinato

Un vettore di un solo elemento è ordinato.Approccio incrementale: passo i: il minimo del sotto-vettore DX (Ai+1 ... An-1) è assegnato a A[i]; incremento di i.Terminazione: tutti gli elementi inseriti ordinatamente.

Selection sort

24/232

Esempio

6 3 5 1 7 21 8 4 12 0 9 8 4

i

13

25/232

Esempio

6 3 5 1 7 21 8 4 12 0 9 8 4

i min di Ai+1, An-1

26/232

Esempio

6 3 5 1 7 21 8 4 12 0 9 8 4

i

14

27/232

Esempio

0 3 5 1 7 21 8 4 12 6 9 8 4

Già ordinati Non ancora considerati

28/232

Esempio

0 3 5 1 7 21 8 4 12 6 9 8 4

i

15

29/232

Esempio

0 3 5 1 7 21 8 4 12 6 9 8 4

i min di Ai+1, An-1

30/232

Esempio

0 3 5 1 7 21 8 4 12 6 9 8 4

16

31/232

Esempio

0 1 5 3 7 21 8 4 12 6 9 8 4

32/232

Implementazione C

void SelectionSort(int A[], int n)

int i, j, min, temp;for(i=0; i<n; i++)

min = i;for (j = i+1; j < n-1; j++)

if (A[j] < A[min])min = j;

temp = A[i];A[i] = A[min];A[min] = temp;

return;

17

33/232

Analisi

Caratteristiche: stabile, in loco.

Due cicli annidati:

esterno: eseguito n-1 volteinterno: all’i-esima iterazione vieneeseguito n-i-1 volte

T(n) = (n-1) + (n-2) +… 2 + 1 = O(n2)

34/232

Counting sort

Ordinamento per calcolo: determinare, per ciascun elemento da ordinare x, quantielementi sono minori di x.

X direttamente assegnato allaposizione finale.

Caratteristiche: stabile, non in loco.

18

35/232

Strutture dati

Si usano 3 vettori:

Vettore di partenza: A[0..n-1] di n interi

Vettore risultato: B [0..n-1] di n interi

Vettore delle occorrenze: C di k interise i dati sono nell’intervallo [0..k-1]

36/232

Algoritmo

Passo 1: occorrenze semplici: C[i] = numero di elementi di A pari ad i

Passo 2: occorrenze multiple: C[i] = numero di elementi di A <= i

Passo 3: ∀ jC[A[j]] = numero di elementi <= A[j]

quindi posizione finale di A[j] in B:B[C[A[j]]-1] = A[j]

19

37/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A Vettore da ordinare

0 1 2 3 4 5 6 7

38/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

0 0 0 0 0 0C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

20

39/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

0 0 1 0 0 0C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

40/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

0 0 1 0 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

21

41/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

0 0 1 1 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

42/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

1 0 1 1 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

22

43/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

1 0 2 1 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

44/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

1 0 2 2 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

23

45/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 0 2 2 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

46/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 0 2 3 0 1C

Vettore da ordinare

Occorrenze semplici

0 1 2 3 4 5 6 7

0 1 2 3 4 5

24

47/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

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

48/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 0 2 3 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

25

49/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 0 2 3 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

50/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 2 3 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

26

51/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 2 3 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

52/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 3 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

27

53/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 3 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

54/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 7 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

28

55/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 7 0 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

56/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 7 7 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

29

57/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 7 7 1C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

58/232

Esempio (n=8, k=6)

2 5 3 0 2 3 0 3A

2 2 4 7 7 8C

Vettore da ordinare

Occorrenze multiple

0 1 2 3 4 5 6 7

0 1 2 3 4 5

30

59/232

Esempio (n=8, k=6)

2 2 4 7 7 8C2 5 3 0 2 3 0 3A

B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

60/232

3

Esempio (n=8, k=6)

2 2 4 7 7 8C2 5 3 0 2 3 0A

B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

31

61/232

3

Esempio (n=8, k=6)

2 2 4 7 7 8C2 5 3 0 2 3 0A

B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

62/232

3

Esempio (n=8, k=6)

2 2 4 7 7 8C2 5 3 0 2 3 0A

3B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

32

63/232

3

Esempio (n=8, k=6)

2 2 4 7 7 8C2 5 3 0 2 3 0A

3B

0 1 3 4 5 6 72 0 1 2 3 4 5

6

0 1 3 4 5 6 72

64/232

0

Esempio (n=8, k=6)

3 2 2 4 6 7 8C2 5 3 0 2 3A

3B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

33

65/232

Esempio (n=8, k=6)

0 3 2 2 4 6 7 8C2 5 3 0 2 3A

3B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

66/232

Esempio (n=8, k=6)

0 3 2 2 4 6 7 8C2 5 3 0 2 3A

3B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

34

67/232

Esempio (n=8, k=6)

0 3 2 2 4 6 7 8C2 5 3 0 2 3A

0 3B

0 1 3 4 5 6 72 0 1 2 3 4 5

0 1 3 4 5 6 72

1

68/232

Implementazione C

#define k 15void CountingSort(int A[],int B[],

int n)int i, j, B C[k]for (i=0; i<k; i++) C[i] = 0;for (i=0; i<n; i++) C[A[i]]++;for (i=1; i<k; i++) C[i] += C[i-1];for (i=n-1; i>=0; i--)

B[C[A[i]]-1] = A[i];C[A[i]]--;

1234

35

69/232

Complessità

Ciclo di inizializzazione di C: O(k)Ciclo di calcolo delle occorrenze semplici: O(n)Ciclo di calcolo delle occorrenze multiple: O(k)Ciclo di ricopiatura in B: O(n)

T(n) = O(n+k).Applicabilità: k=O(n), quindi T(n) = O(n).

1

234

70/232

Algoritmi e Programmazione Avanzata - teoria

36

71/232

Merge Sort 1/2

Ricorsivo, “divide et impera”

Stabile

Divisione:due sottovettori SX e DX rispetto alcentro del vettore.

p r

72/232

Merge Sort 1/2

Ricorsivo, “divide et impera”

Stabile

Divisione:due sottovettori SX e DX rispetto alcentro del vettore.

p r

37

73/232

Merge Sort 1/2

Ricorsivo, “divide et impera”

Stabile

Divisione:due sottovettori SX e DX rispetto alcentro del vettore.

p r

p rq q+1

74/232

Merge Sort 2/2

Ricorsionemerge sort su sottovettore DXmerge sort su sottovettore SXcondizione di terminazione: con 1 (p=r) o 0 (p>r) elementi è ordinato

Ricombinazione:fonde i due sottovettori ordinati in un vettore ordinato.

38

75/232

Esempio

12 6 4 5 9 2 3 1

Divisione ricorsiva:

76/232

Esempio

12 6 4 5 9 2 3 1

Divisione ricorsiva:

39

77/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

Divisione ricorsiva:

78/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

Divisione ricorsiva:

40

79/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6

Divisione ricorsiva:

80/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6

Divisione ricorsiva:

41

81/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6

12

Divisione ricorsiva:

82/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6

12 6

Divisione ricorsiva:

42

83/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6 4 5

12 6

Divisione ricorsiva:

84/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6 4 5

12 6

Divisione ricorsiva:

43

85/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6 4 5

12 6 4

Divisione ricorsiva:

86/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5

12 6 4 5

12 6 54

Divisione ricorsiva:

44

87/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6 4 5

12 6 54

Divisione ricorsiva:

88/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6 4 5

12 6 54

Divisione ricorsiva:

45

89/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6 4 5 9 2

12 6 54

Divisione ricorsiva:

90/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6 4 5 9 2

12 6 54

Divisione ricorsiva:

46

91/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6

9

4 5 9 2

12 6 54

Divisione ricorsiva:

92/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6

9

4 5 9 2

12 6 54 2

Divisione ricorsiva:

47

93/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6

9

4 5 9 2 3 1

12 6 54 2

Divisione ricorsiva:

94/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6

9

4 5 9 2 3 1

12 6 54 2

Divisione ricorsiva:

48

95/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6

9

4 5 9 2 3 1

12 6 54 2 3

Divisione ricorsiva:

96/232

Esempio

12 6 4 5 9 2 3 1

12 6 4 5 9 2 3 1

12 6

9

4 5 9 2 3 1

12 6 54 2 3 1

Divisione ricorsiva:

49

97/232

Esempio

Ricombinazione:

98/232

Esempio

Ricombinazione:

12

50

99/232

Esempio

Ricombinazione:

12 6

100/232

Esempio

Ricombinazione:

6 12

12 6

51

101/232

Esempio

Ricombinazione:

6 12

12 6 4

102/232

Esempio

Ricombinazione:

6 12

12 6 54

52

103/232

Esempio

Ricombinazione:

6 12 4 5

12 6 54

104/232

Esempio

Ricombinazione:

4 5 6 12

6 12 4 5

12 6 54

53

105/232

Esempio

Ricombinazione:

4 5 6 12

6 12

9

4 5

12 6 54

106/232

Esempio

Ricombinazione:

4 5 6 12

6 12

9

4 5

12 6 54 2

54

107/232

Esempio

Ricombinazione:

4 5 6 12

6 12

9

4 5 2 9

12 6 54 2

108/232

Esempio

Ricombinazione:

4 5 6 12

6 12

9

4 5 2 9

12 6 54 2 3

55

109/232

Esempio

Ricombinazione:

4 5 6 12

6 12

9

4 5 2 9

12 6 54 2 3 1

110/232

Esempio

Ricombinazione:

4 5 6 12

6 12

9

4 5 2 9 1 3

12 6 54 2 3 1

56

111/232

Esempio

Ricombinazione:

4 5 6 12 1 2 3 9

6 12

9

4 5 2 9 1 3

12 6 54 2 3 1

112/232

Esempio

Ricombinazione:

1 2 3 4 5 6 9 12

4 5 6 12 1 2 3 9

6 12

9

4 5 2 9 1 3

12 6 54 2 3 1

57

113/232

Implementazione C

void MergeSort(int A[], int p, int r)

int q;

if (p < r) q = (p + r)/2;MergeSort(A, p, q);MergeSort(A, q+1, r);

Merge(A, p, q, r);return;

114/232

Implementazione C

void Merge(int A[], int p, int q, int r)int B[MAX], i, j, k;

for (i=p, j=q+1, k=p; i<=q && j<=r; )if ( A[i] < A[j] ) B[k++] = A[i++];else B[k++] = A[j++];

for ( ; i<=q; ) B[k++] = A[i++];for ( ; j<=r; ) B[k++] = A[j++];for ( k=p; k<=r; k++ ) A[k] = B[k];return;

58

115/232

Complessità 1/3

Ipotesi: n = 2k

Dividi: calcola la metà di un vettore D(n)=Θ(1)

Risolvi: risolve 2 sottoproblemi di dimensionen/2 ciascuno

2T(n/2)Terminazione: semplice test

Θ(1)Combina: basata su Merge

C(n) = Θ(n)

116/232

Complessità 2/3

Equazione alle ricorrenze

T(n) = 2T(n/2) + n n ≥ 2T(1) = 1

Soluzione:T(n) = Θ(n lg n)

59

117/232

Complessità 3/3

Intuitivamente:

log 2

n

Operazioni totali: n log2 n

Livelli di ricorsione: log2 n Operazioni per livello: n

118/232

Quicksort 1/2

Ricorsivo, “divide et impera”

In loco

Divisione:partiziona il vettore A[p..r] in due sottovettoriSX e DX:

- dato un elemento pivot x- SX A[p..q] contiene tutti elementi ≤ x- DX A[q+1..r] contiene tutti elementi ≥ x- la divisione non è necessariamente a metà

60

119/232

Quicksort 2/2

Ricorsionequicksort su sottovettore SX A[p..q]quicksort su sottovettore DX A[q+1..r]condizione di terminazione: se il vettore ha1 elemento è ordinato

Ricombinazione:nulla

120/232

Algoritmi e Programmazione Avanzata - teoria

61

121/232

Partition

Pivot x = A[p]

Individua A[i] e A[j] elementi “fuori posto”ciclo discendente j fino a trovare un elemento minore del pivot x

ciclo ascendente su i fino a trovare unelemento maggiore del pivot x

Scambia A[i] e A[j]

Ripeti fintanto che i < j

T(n) = Θ(n)

122/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j

62

123/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j5 3 2 6 4 1 3 7A

ji

124/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j5 3 2 6 4 1 3 7A

ji

63

125/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j5 3 2 6 4 1 3 7A

j

3 3 2 6 4 1 5 7A

j

i

i

126/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j5 3 2 6 4 1 3 7A

j

3 3 2 6 4 1 5 7A

j

i

i

64

127/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j5 3 2 6 4 1 3 7A

j

3 3 2 6 4 1 5 7A

j

i

i

3 3 2 1 4 6 5 7A

j i

128/232

Esempio di Partition

5 3 2 6 4 1 3 7 5xAp r

i j5 3 2 6 4 1 3 7A

j

3 3 2 6 4 1 5 7A

j

i

i

3 3 2 1 4 6 5 7A

j iq

65

129/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

130/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

66

131/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 1x

132/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 1x

1

67

133/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 1x

1 2

134/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 3 3 41x 3x

1 2

68

135/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 3 3 41x 3x

1 2 3

136/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 3 3 41x 3x

1 2 3 3 4 3x

69

137/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 3 3 41x 3x

1 2 3 3 4 3x

3

138/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 3x

1 2 3 3 41x 3x

1 2 3 3 4 3x

3 4

70

139/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 6 5 73x 6x

1 2 3 3 41x 3x

1 2 3 3 4 3x

3 4

140/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 6 5 73x 6x

51 2 3 3 41x 3x

1 2 3 3 4 3x

3 4

71

141/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 6 5 73x 6x

5 6 7 6x1 2 3 3 41x 3x

1 2 3 3 4 3x

3 4

142/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 6 5 73x 6x

5 6 7 6x

6

1 2 3 3 41x 3x

1 2 3 3 4 3x

3 4

72

143/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 6 5 73x 6x

5 6 7 6x

6 7

1 2 3 3 41x 3x

1 2 3 3 4 3x

3 4

144/232

Esempio di Quicksort

5 3 2 6 4 1 3 7 5xA

3 3 2 1 4 6 5 73x 6x

5 6 7 6x

6 7

1 2 3 3 41x 3x

1 2 3 3 4 3x

3 41 2 3 3 4 5 6 7A

73

145/232

Implementazione C

int partition ( int A[], int p, int r )int x, i, j, temp;

x = A[p]; i=p-1; j=r+1while (i < j)

while(A[--j] > x);while(A[++i] < x);if (i< j)

temp = A[i];A[i] = A[j];A[j] = temp;

return(j);

146/232

Implementazione C

Void quicksort ( int A[], int p, int r )int q;

if (p < r)

q = partition(A, p, r);

quicksort(A, p, q);quicksort(A, q+1, r);

return;

74

147/232

Complessità

Efficienza legata al bilanciamento delle partizioni

A ogni passo partition ritorna:caso peggiore un vettore da n-1 elementie l’altro da 1caso migliore due vettori da n/2 elementicaso medio due vettori di dimensionidiverse

Bilanciamento legato alla scelta del pivot

148/232

Caso peggiore 1/2

Caso peggiore: pivot = minimo o massimo(vettore già ordinato)

Equazione alle ricorrenze:T(n) = T(n-1) + n n>=2

T(1) = 1

T(n) = Θ(n2)

75

149/232

Caso peggiore 2/2

n n

150/232

Caso peggiore 2/2

n

1 n-1

n

n

76

151/232

Caso peggiore 2/2

n

1 n-1

1 n-2

n

n

n-1

152/232

Caso peggiore 2/2

n

1 n-1

1 n-2

1 n-3

n

n

n-1

n-2

77

153/232

Caso peggiore 2/2

n

1 n-1

1 n-2

1 n-3

n

n

n-1

n-2...

154/232

Caso peggiore 2/2

n

1 n-1

1 n-2

1 n-3

2

n

n

n-1

3

n-2...

78

155/232

Caso peggiore 2/2

n

1 n-1

1 n-2

1 n-3

1 1

2

n

n

n-1

3

n-2...

2

156/232

Caso peggiore 2/2

n

1 n-1

1 n-2

1 n-3

1 1

2

n

n

n-1

3

n-2...

2

n

79

157/232

Caso peggiore 2/2

n

1 n-1

1 n-2

1 n-3

1 1

2

n

n

n-1

3

n-2...

2T(n) = Θ(n2)

n

158/232

Caso migliore 1/2

Equazione alle ricorrenze:

T(n) = 2T(n/2) + n n>=2

T(1) = 1

T(n) = Θ(n lg n)

80

159/232

Caso migliore 2/2

n n

160/232

Caso migliore 2/2

n

n/2 n/2 n

n

81

161/232

Caso migliore 2/2

n

n/2 n/2

n/4 n/4 n/4 n/4

n

n

n

162/232

Caso migliore 2/2

n

n/2 n/2

n/4 n/4 n/4 n/4

n

n

n

82

163/232

Caso migliore 2/2

n

n/2 n/2

n/4 n/4 n/4 n/4

1 1 1 1 1 1 1 1

n

n

n

n

164/232

Caso migliore 2/2

n

n/2 n/2

n/4 n/4 n/4 n/4

1 1 1 1 1 1 1 1

n

n

n

n

lg n

83

165/232

Caso migliore 2/2

T(n) = Θ(n lg n)

n

n/2 n/2

n/4 n/4 n/4 n/4

1 1 1 1 1 1 1 1

n

n

n

n

lg n

166/232

Caso medio 1/2

Purché non si ricada nel caso peggiore, anche se il partizionamento è molto sbilanciato, caso medio = caso migliore

Esempio: ad ogni passo si generano 2 partizioni, la prima con 9/10 n e la seconda con n/10 elementi.

84

167/232

Caso medio 2/2

n n

168/232

Caso medio 2/2

n

n/10 9n/10 n

n

85

169/232

Caso medio 2/2

n

n/10 9n/10

n/100 9n/100 9n/100 81n/100

n

n

n

170/232

Caso medio 2/2

n

n/10 9n/10

n/100 9n/100 9n/100 81n/100

1

n

n

n

86

171/232

Caso medio 2/2

n

n/10 9n/10

n/100 9n/100 9n/100 81n/100

1

1

n

n

n

n

172/232

Caso medio 2/2

n

n/10 9n/10

n/100 9n/100 9n/100 81n/100

1

1

n

n

n

n

log 1

0n

log10/9 n

87

173/232

Caso medio 2/2

T(n) = Θ(n lg n)

n

n/10 9n/10

n/100 9n/100 9n/100 81n/100

1

1

n

n

n

nlo

g 10

n

log10/9 n

174/232

Scelta del pivot

Elemento a caso: genera un numerocasuale i con p ≤ i ≤ r, poi scambia A[p] e A[i], usando come pivot A[p]

Elemento di mezzo: x ← A[(p+r)/2]

Scegliere il valore medio tra min e max

Scegliere la mediana tra 3 elementi presia caso nel vettore

…

88

175/232

Algoritmi e Programmazione Avanzata - teoria

176/232

Definizione: albero binario conproprietà strutturale: quasi completo (tutti i livelli completi, tranne eventualmente l’ultimo, riempito da SX a DX) ⇒ quasi bilanciato

proprietà funzionale:∀ i ≠ r key(parent(i)) ≥ key(i)

conseguenza: chiave max nella radice

Heap 1/2

89

177/232

Operazioni:Heapify(A,i)BuildHeap(A) HeapSort(A)

Heap 2/2

178/232

Definizione: struttura dati per mantenere un set S di n elementi a ciascuno dei quali è associata una priorità.

Operazioni:insert(S, x) maximum(S) Θ(1)extract_max(S) O(lg n)

Implementazione: con heap.

Code a priorità

90

179/232

Esempio

20

15 10

5 4

-1 0

12 11

9 8 5 7

180/232

Struttura dati: vettore A[0..length(A)-1]heapsize(A): numero di elementi in heap ARadice in A[0]Dato A[i]:

figlio SX in A[2i+1]figlio DX in A[2i+2].

Implementazione

91

181/232

Esempio

20

15 10

5 4

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12

20 15 10 12 11 5 4 9 8 6 7 -1 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15

A

length(A)=16

heapsize(A)=13i 0

182/232

Dato n = heapsize(A):i < nse i < n/2-1, il nodo i ha due figlise i = n/2-1, il nodo i ha uno (n pari)o due (n dispari) figlise i > n/2-1, il nodo i non ha alcun figlio

Esempio

92

183/232

Aggiunge una foglia all’albero (cresce per livelli da SX a DX, rispettando la proprietà strutturale)

Risale dalla foglia fino al più alla radice confrontando con la chiave da inserire e facendo eventualmente scendere la chiave del padre nel figlio

Inserisce la chiave nel nodo corrente

Procedura Insert

Complessità: T(n) = O(lg n)

184/232

Esempio

20

15 10

5 4

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12

Inserzione di 17

93

185/232

Esempio

20

15

5 4

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

Creo foglia10

186/232

Confronto 17 e 4 e faccio scendere 4

Esempio

20

15

5 4

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

10

94

187/232

Esempio

20

15

5

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

4

Confronto 17 e 4 e faccio scendere 4

10

188/232

Esempio

20

15

5

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

4

Confronto 17 e 10 e faccio scendere 10

10

95

189/232

Esempio

20

15

5

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

4

10

Confronto 17 e 10 e faccio scendere 10

190/232

Esempio

20

15

5

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

4

10

Inserisco 17

96

191/232

Esempio

20

15

5

-1 0

12 11

9 8 6 7

0

1 2

3 4 5 6

7 8 9 10 11 12 13

4

10

17

Inserisco 17

192/232

Codice

#define PARENT(i) ((i-1) / 2)void Insert(int A[], int x, int heapsize)

int i;i = ++heapsize;while (i>1 && A[PARENT(i)] < x)

A[i] = A[PARENT(i)];i = PARENT(i);

A[i] = x;return;

97

193/232

Procedura Heapify

Trasforma in heap i, Left(i), Right(i), dove Left(i) e Right(i) sono già heap

Assegna ad A[i] il max tra A[i], Left(i) e Right(i)

Se c’è stato scambio A[i] ↔ Left(i), applica ricorsivamente heapify su sottoalbero con radice Left(i)

Analogamente per scambio A[i] ↔ Right(i)

Complessità: T(n) = O(lg n)

194/232

Esempio

16

4 10

9 314 7

2 8 1

0

1 2

3 4 5 6

7 8 9

98

195/232

Esempio

16

4 10

9 314 7

2 8 1

0

1 2

3 4 5 6

7 8 9

Heapify(A, 1)

i = 1

196/232

Esempio

16

4 10

9 314 7

2 8 1

0

1 2

3 4 5 6

7 8 9

Heapify(A, 1)14 = max(4, 14, 7)

i = 1

99

197/232

Esempio

16

4 10

9 314 7

2 8 1

0

1 2

3 4 5 6

7 8 9

Heapify(A, 1)14 = max(4, 14, 7)

i = 1

Left (i) Right(i)

198/232

Esempio

16

4 10

9 314 7

2 8 1

0

1 2

3 4 5 6

7 8 9

Heapify(A, 1)14 = max(4, 14, 7)A[i] ↔ A[Left(i)]

i = 1

Left (i) Right(i)

100

199/232

Esempio

16

14 10

9 34 7

2 8 1

0

1 2

3 4 5 6

7 8 9

200/232

Esempio

Heapify(A, 3)

16

14 10

9 34 7

2 8 1

0

1 2

3 4 5 6

7 8 9

i = 3

101

201/232

Esempio

Heapify(A, 3)8 = max(4, 2, 8)

16

14 10

9 34 7

2 8 1

0

1 2

3 4 5 6

7 8 9

i = 3

202/232

Esempio

Heapify(A, 3)8 = max(4, 2, 8)

16

14 10

9 34 7

2 8 1

0

1 2

3 4 5 6

7 8 9

i = 3

Left (i) Right(i)

102

203/232

Esempio

Heapify(A, 3)8 = max(4, 2, 8)A[i] ↔ A[Right(i)]Heapify(A, 8)16

14 10

9 34 7

2 8 1

0

1 2

3 4 5 6

7 8 9

i = 3

Left (i) Right(i)

204/232

Esempio

16

14 10

9 38 7

2 4 1

0

1 2

3 4 5 6

7 8 9

103

205/232

Esempio

Heapify(A, 8)fogliaterminazione.16

14 10

9 38 7

2 4 1

0

1 2

3 4 5 6

7 8 9

i = 8

206/232

Codice

#define LEFT(i) ((i*2) + 1)#define RIGHT(i) ((i*2) + 2)void Swap( int v[], int n1, int n2)

int temp;temp = v[n1];v[n1] = v[n2];v[n2] = temp;return;

104

207/232

Codice

void Heapify(int A[], int i, int heapsize)

int l, r, largest;l = LEFT(i);r = RIGHT(i); if (l<heapsize && A[l]>A[i]) largest=l;else largest = i;if (r<heapsize && A[r]>A[largest]) largest=r;if (largest != i)

Swap(A,i,largest);Heapify(A,largest,heapsize);

return;

208/232

Procedura BuildHeap

Trasforma un albero binario memorizzato in vettore A in un heap:

le foglie sono heapapplica Heapify a partire dal padre dell’ultima coppia di foglie fino alla radice

Complessità: T(n)= O(n)

105

209/232

Esempio

4

1 3

9 102 16

14 8 7

0

1 2

3 4 5 6

7 8 9

210/232

Esempio

4

1 3

9 102 16

14 8 7

0

1 2

3 4 5 6

7 8 9

BuildHeap(A)

106

211/232

Esempio

4

1 3

9 102 16

14 8 7

0

1 2

3 4 5 6

7 8 9

BuildHeap(A)

Heapify(A, 4)

212/232

Esempio

4

1 3

9 102 16

14 8 7

0

1 2

3 4 5 6

7 8 9

BuildHeap(A)

107

213/232

Esempio

4

1 3

9 102 16

14 8 7

0

1 2

3 4 5 6

7 8 9

Heapify(A, 3)

214/232

Esempio

4

1 3

9 10

2

1614

8 7

0

1 2

3 4 5 6

7 8 9

108

215/232

Esempio

4

1 3

9 10

2

1614

8 7

0

1 2

3 4 5 6

7 8 9

Heapify(A, 2)

216/232

Esempio

4

7

39

10

2

14

8

0

1 2

3 4 5 6

7 8 9

1

16

109

217/232

Esempio

4

39

10

2

14

8

0

1 2

3 4 5 6

7 8 9

Heapify(A, 1)

7

1

16

218/232

Esempio

16

7

39

10

2

14

8

1

0

1 2

3 4 5 6

7 8 9

4

110

219/232

Esempio

16

1

39

10

2

14

8

7

0

1 2

3 4 5 6

7 8 9

4

220/232

Esempio

16

1

39

10

2

14

8

7

0

1 2

3 4 5 6

7 8 9

4

Heapify(A, 0)

111

221/232

Esempio

4

1

39

10

2

14

8

7

0

1 2

3 4 5 6

7 8 9

16

222/232

Esempio

14

1

39

10

2

4

8

7

0

1 2

3 4 5 6

7 8 9

16

112

223/232

Esempio

14

1

39

10

2

8

4

7

0

1 2

3 4 5 6

7 8 9

16

224/232

Codice

void BuildHeap (int A[], int heapsize)

int i;for (i=heapsize/2-1; i >= 0; i--)

Heapify(A,i,heapsize);return;

113

225/232

Procedura HeapSort

Trasforma il vettore in uno heapScambia il primo e ultimo elemento Riduci la dimensione dello heap di 1Ripristina la proprietà di heapRipeti fino a esaurimento dello heap

Complessità: T(n)= (n lg n)

226/232

Esempio

5 3 2 6 4 1 9 7A

5

3 2

1 96 4

7

0

1 2

3 4 5 6

7

Configurazione iniziale

114

227/232

Esempio

A

0

1 2

3 4 5 6

7

Applico Build_heap heapsize

9 7 5 6 4 1 2 3

9

7 5

1 26 4

3

228/232

Esempio

A

0

1 2

3 4 5 6

7

A[0] ↔ A[heapsize-1]heapsize--

heapsize

9 7 5 6 4 1 2 3

7 5

1 26 4

3 7 5 6 4 1 2 9

3

7

9

115

229/232

Esempio

A

0

1 2

3 4 5 6

7

Heapify(A, 0) heapsize

9 7 5 6 4 1 2 33 7 5 6 4 1 2 97 6 5 3 4 1 2 9

7

6 5

23 4

9

1

230/232

Esempio

A

0

1 2

3 4 5 6

7

A[0] ↔ A[heapsize-1]heapsize--

heapsize

9 7 5 6 4 1 2 33 7 5 6 4 1 2 92 6 5 3 4 1 7 9

2

6 5

73 4

9

1

116

231/232

Esempio

A

0

1 2

3 4 5 6

7

Heapify(A, 0) heapsize

9 7 5 6 4 1 2 33 7 5 6 4 1 2 96 4 5 3 2 1 7 9

6

4 5

1 73 2

9

232/232

Codice

void HeapSort(int A[], int heapsize)

int i;BuildHeap(A, heapsize);for (i=heapsize-1; i > 0; i--)

Swap (A,0,i);heapsize--;Heapify(A,0,heapsize);

return;