Algoritmi e Strutture Dati Capitolo 4 Ordinamento Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Ordinamento Dato un insieme S di n oggetti presi da un dominio totalmente ordinato, ordinare S • Esempi: ordinare una lista di nomi alfabeticamente, o un insieme di numeri, o un insieme di compiti d’esame in base al cognome dello studente • Subroutine in molti problemi • E’ possibile effettuare ricerche in array ordinati in tempo O(log n) 2 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Il problema dell’ordinamento • Input: una sequenza di n numeri <a1,a2,…,an> • Output: una permutazione (riarrangiamento) <ai1, ai2,…, ain> della sequenza di input tale che ai1 ai2 … ain 3 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano SelectionSort Approccio incrementale: estende l’ordinamento da k a k+1 elementi, scegliendo il minimo degli n-k elementi non ancora ordinati e mettendolo in posizione k+1 4 7 2 4 5 3 1 1 2 3 4 5 7 1 2 4 5 3 7 1 2 3 4 5 7 1 2 4 5 3 7 1 2 3 4 5 7 1 2 3 5 4 7 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano SelectionSort (A) 1. for k=0 to n-2 do 2. m = k+1 3. for j=k+2 to n do 4. 5. NOTA: Assumiamo che il primo elemento dell’array sia in A[1] if (A[j] < A[m]) then m=j scambia A[m] con A[k+1] • All’inizio del generico passo k, k=0,…,n-2, A[1],…,A[k] sono già ordinati (per k=0, nulla è ordinato) • linee 2-4: ricerca del minimo fra gli elementi A[k+1],…,A[n] • m è l’indice dell’array in cui si trova il minimo • il minimo è spostato in posizione k+1 • al fine del generico passo k, k=0,…,n-2, A[1],…,A[k+1] sono ordinati 5 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Correttezza • Si dimostra facendo vedere che alla fine del generico passo k (k=0,…,n-2) si ha: (i) i primi k+1 elementi sono ordinati e (ii) contengono i k+1 elementi più piccoli dell’array • Induzione su k: – k=0: Alla prima iterazione viene semplicemente selezionato l’elemento minimo dell’array (i) e (ii) banalmente verificate. – k>0. All’inizio del passo k i primi k elementi sono ordinati e sono i k elementi più piccoli nell’array (ipotesi induttiva). Allora la tesi segue dal fatto che l’algoritmo seleziona il minimo dai restanti n-k elementi e lo mette in posizione k+1. Infatti: (ii) i k+1 elementi restano i minimi nell’array (i) l’elemento in posizione k+1 non è mai più piccolo dei primi k 6 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Complessità temporale SelectionSort (A) 1. for k=0 to n-2 do 2. m = k+1 1 assegnamento 3. for j=k+2 to n do n-k-1 confronti 4. 5. if (A[j] < A[m]) then m=j scambia A[m] con A[k+1] n-2 n-1 k=0 k=1 il tutto eseguito n-1 volte 1 scambio (3 assegnamenti) T(n) = [1+(n-k-1)+3]= (k+4) = n·(n-1)/2+4·(n-1)= (n2) Tworst(n) = Tbest(n) = Tavg(n) = (n2) 7 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano InsertionSort Approccio incrementale: estende l’ordinamento da k a k+1 elementi, posizionando l’elemento (k+1)-esimo nella posizione corretta rispetto ai primi k elementi 8 7 2 4 5 3 1 2 4 5 7 3 1 2 7 4 5 3 1 2 3 4 5 7 1 2 4 7 5 3 1 1 2 3 4 5 7 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano InsertionSort (A) 1. for k=1 to n-1 do 2. x = A[k+1] 3. for j=1 to k+1 do 4. 5. if (A[j] > x) then break if (j < k+1) then 6. for t=k downto j do A[t+1]= A[t] 7. A[j]=x • • • • • 9 All’inizio del generico passo k, A[1],…,A[k] sono già ordinati elemento x=A[k+1] inserito nella posizione che gli compete righe 3 e 4: individuano la posizione j in cui va messo x riga 6: fa spazio per inserire x Alla fine del generico passo k, A[1],…,A[k+1] sono ordinati Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Correttezza • Si dimostra facendo vedere che alla fine del generico passo k (k=1,…,n-1) i primi k+1 elementi sono ordinati (si noti la differenza con il Selection Sort, in cui invece dovevo far vedere che erano i più piccoli) • Induzione su k: – k=1: banale: si riordinano A[1] e A[2]; – k>1: All’inizio del passo k i primi k elementi sono ordinati (ipotesi induttiva). Allora la tesi segue dalla struttura dell’algoritmo, il quale inserisce A[k+1] nella giusta posizione della sequenza 10 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Complessità temporale • Notazione asintotica • Quando parliamo di complessità di un algoritmo, ci riferiamo implicitamente al caso peggiore • Ne consegue che è sufficiente considerare le cosidette operazioni dominanti, ovvero quelle che nel caso peggiore vengono eseguite più spesso • Queste si trovano annidate nei cicli più interni dello pseudocodice che descrive l’algoritmo 11 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Complessità temporale InsertionSort (A) 1. for k=1 to n-1 do 2. x = A[k+1] 3. for j=1 to k+1 do 4. if (A[j] > x) then break 5. t≤k+1 confronti if (j < k+1) then 6. for t=k downto j do A[t+1]= A[t] 7. A[j]=x k+1–t assegnamenti k+1 oper. il tutto eseguito n-1 volte n-1 T(n) = (k+1) = (n2) k=1 Tworst(n) = Tbest(n) = Tavg(n) = (n2) Possiamo fare meglio? 12 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Complessità spaziale Ricordiamo che oltre alla complessità temporale dobbiamo valutare anche la complessità spaziale di un algoritmo, ovvero lo spazio di memoria necessario per ospitare le strutture di dati utilizzate dall’algoritmo. La complessità spaziale del Selection Sort e dell’Insertion Sort è Θ(n) Nota: Se la complessità spaziale di un certo algoritmo è (g(n)) e tale algoritmo per sua natura è costretto ad “ispezionare” l’intera memoria occupata, allora la complessità temporale dell’algoritmo è (g(n)). 13 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Conseguenze per il problema dell’ordinamento La complessità spaziale di qualsiasi algoritmo che risolve il problema dell’ordinamento è (n)… …ma qualsiasi algoritmo che risolve il problema dell’ordinamento deve ispezionare tutti i dati in ingresso, e quindi ha complessità temporale T(n)=(n) Il problema dell’ordinamento ha delimitazione inferiore (lower bound) alla complessità temporale (n). 14 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Complessità temporale InsertionSort2 (A) 1. for k=1 to n-1 do 2. x = A[k+1] 3. j=k 4. while j > 0 e A[j] > x do 5. tk ≤ 2k assegnam. A[j+1] = A[j] 6. j= j-1 7. A[j+1]=x n-1 il tutto eseguito n-1 volte n-1 T(n) = tk ≤ 2k k=1 k=1 T(n) = O(n2) 15 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Caso migliore, peggiore, medio • Caso migliore – array già ordinato in ordine crescente tk = 0 Tbest(n) = (n) (costo del ciclo for esterno) • Caso peggiore – array ordinato in ordine decrescente tk = 2k n-1 T(n):= Tworst(n)= 2k = (n2) k=1 • Caso medio – array disordinato tk = k n-1 Tavg(n)= k = (n2) k=1 16 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Esercizi di approfondimento Illustrare l’evoluzione di Insertion-Sort applicata all’array A=<31,41,59,26,41,58> • • Riscrivere la procedura di Insertion-Sort per ordinare in modo non crescente 17 Copyright © 2004 - The McGraw - Hill Companies, srl