Ordinamento (algoritmi quadratici) PDF

Ordinamento (algoritmi quadratici) March 12, 2020 Obiettivi: attraverso lo studio degli algoritmi di ordinamento quadratici, applicare la nozione di invariante e introdurre l'analisi di complessità. Argomenti: problema dell'ordinamento, inse...

Ordinamento (algoritmi quadratici) March 12, 2020 Obiettivi: attraverso lo studio degli algoritmi di ordinamento quadratici, applicare la nozione di invariante e introdurre l'analisi di complessità. Argomenti: problema dell'ordinamento, insertion-sort e selection-sort con analisi di correttezza e comp- lessità. 1 Problema dell'ordinamento (sorting) La ricerca in un vettore di n elementi richiede n confronti nel caso peggiore. Se il vettore è ordinato, si può applicare la ricerca binaria (ricerca dicotomica) che richiede al più log2 n confronti: BinSearch-Ric(x, A, i, j ). Pre: A[i..j] ordinato. Post: true se x ∈ A[i..j] if i > j then. A[i..j] = ∅ return f alse else m ← b(i + j)/2c ifx = A[m] then return true else if x < A[m] then return BinSearch-Ric(x, A, i, m − 1) else. A[m] < x return BinSearch-Ric(x, A, m + 1, j) end if end if end if Per ordinare un vettore, si potrebbe pensare di generare tutte le permutazioni e scegliere quella nella quale gli elementi sono ordinati: Sorted(A[1..n]) for i ← 2 to n do ifA[i − 1] > A[i] then return false end if end for return true 1  Trivial-Sort(A) for all A0 permutazione di A do 0 if Sorted(A ) then return A0 end if end for Ma il numero di permutazioni è n! che cresce più velocemente di 2n. Non è praticabile. 2 Insertion-sort L'idea generale: data un vettore con la parte sinistra, A[1..i − 1], ordinata, è facile inserirci l'elemento A[i] in modo tale che il sottovettore A[1..i] risulti ordinata (aumentando così la parte ordinata). Punto di partenza: i=2 (così la parte a sinistra di A[i] contiene un singolo elemento e quindi è ordinata). 0: Insertion-Sort(A[1..n]) 1: for i ← 2 to n do 2: j←i 3: while j > 1 and A[j − 1] > A[j] do 4: scambia A[j − 1] con A[j] 5: j ←j−1 6: end while 7: end for Simulazione con A = (2, 6, 3, 1, 5, 4). La parte ordinata del vettore viene scritto in grassetto. Il numero che deve essere inserito al posto giusto viene scritto in corsivo. i = 2, j = 2 : (2,6,3,1,5,4) i = 3, j = 3 : (2,6,3,1,5,4) i = 3, j = 2 : (2,3,6,1,5,4) i = 4, j = 4 : (2,3,6,1,5,4) i = 4, j = 3 : (2,3,1,6,5,4) i = 4, j = 2 : (2,1,3,6,5,4) i = 4, j = 1 : (1,2,3,6,5,4) i = 5, j = 5 : (1,2,3,6,5,4) i = 5, j = 4 : (1,2,3,5,6,4) i = 6, j = 6 : (1,2,3,5,6,4) i = 6, j = 5 : (1,2,3,5,4,6) i = 6, j = 4 : (1,2,3,4,5,6) i = 7 : (1,2,3,4,5,6) 2.1 Dimostrazione della correttezza con invarianti Invariante del ciclo esterno: il sottovettore A[1..i − 1] è ordinato. Inizializzazione: con i=2 è vero (fa riferimento ad un vettore di un singolo elemento). Mantenimento: assumendo che il ciclo interno inserisci al posto giusto A[i] (la dimostreremo di seguito) l'invariante viene mantenuta. All'uscita: con i=n+1 l'invariante implica che il vettore è ordinato. Invariante del ciclo interno: i vettori A[1..j − 1] e A[j..i] sono ordinati ∧ ∀l, 1 ≤ l ≤ j − 1, ∀k, j + 1 ≤ k ≤ i.A[l] ≤ A[k] 2 dove la seconda parte esprime il fatto che ciascun elemento in A[1..j − 1] è minor uguale di qualunque elemento in A[j + 1..i]. Inizializzazione: grazie all'invariante del ciclo esterno e al valore iniziale di j=i l'invariante vale. Mantenimento: come ipotesi induttiva assumiamo che l'invariante vale prima di eseguire il corpo del ciclo; ci sono due possibilità: 1. se A[j − 1] ≤ A[j] ∨ j = 1 allora si esce dal ciclo e all'uscita, grazie al fatto che A[j − 1] ≤ A[j] ≤ A[j + 1] (dove la parte destra c'è solo so j 6= i e la parte sinistra solo se j 6= 1) e all'ipotesi induttiva, tutto il sotto vettore A[1..i] è ordinato, 2. se A[j − 1] < A[j] allora si fa lo scambio fra A[j − 1] e A[j] e l'invariante rimane valido All'uscita: discusso al punto 1. sopra. Quindi l'algoritmo Insertion-Sort è corretto. 2.2 Tempo di esecuzione del Insertion-Sort Calcoliamo il tempo di esecuzione assumendo che eseguire la riga i, 1 ≤ i ≤ 5, una volta richiede ci unità di tempo. La riga 1 viene eseguita con i = 2, 3,..., n, n + 1, cioè n volte (viene eseguita con i = n+1 perché bisogna accorgersi di dover uscire dal ciclo). La riga 2 viene eseguita con i = 2, 3,..., n, cioè n − 1 volte. Dato un valore per i, denotiamo con ti il numero di volte che la riga 3 viene eseguita. Nel caso migliore ti = 1 (non servono scambi per inserire A[i] al posto giusto) e nel caso peggiore ti = i (bisogna portare A[i] all'inizio del vettore e quindi la condizione del while viene valutata con j = i, i − 1,..., 2, 1). In totale la riga Pn 3 viene eseguita i=2 ti volte. La riga 4 viene eseguita ti − 1 volta dato un valore per i (una volta in meno rispetto alla riga 3). In totale Pn la riga 4 viene eseguita i=2 (ti − 1) volte. La riga 5 viene eseguita ti − 1 volta dato un valore per i (una volta in meno rispetto alla riga 3). In totale Pn la riga 5 viene eseguita i=2 (ti − 1) volte. Considerando il caso peggiore (cp) il tempo di esecuzione è n X n X n X Tcp (n) = c1 n + c2 (n − 1) + c3 i + c4 (i − 1) + c5 (i − 1) = i=2 i=2 i=2 2+n 1+n−1 (c1 + c2 )n − c2 + c3 (n − 1) + (c4 + c5 ) (n − 1) 2 2 Segue che Tcp (n) è un polinomio di secondo grado in n, cioè può essere espresso come Tcp (n) = an2 + bn + c Di conseguenza, per valori grandi di n, Tcp (n) ≈ an2 e quindi il tempo di esecuzione nel caso peggiore è proporzionale al quadrato del numero di elementi del vettore. Nel caso peggiore l'algoritmo è quadratico. Considerando il caso migliore (cm) il tempo di esecuzione è n X n X n X Tcm (n) = c1 n + c2 (n − 1) + c3 1 + c4 (1 − 1) + c5 (1 − 1) = i=2 i=2 i=2 (c1 + c2 )n − c2 + c3 (n − 1) Segue che Tcm (n) è un polinomio di primo grado in n, cioè può essere espresso come Tcm (n) = an + b 3 Di conseguenza, per valori grandi di n, Tcm (n) ≈ an e quindi il tempo di esecuzione nel caso migliore è proporzionale al numero di elementi del vettore. Nel caso migliore l'algoritmo è lineare. 3 Selection-sort L'idea generale: data un vettore in cui la parte sinistra, A[1..i − 1], è ordinata e contiene gli i − 1 numeri più piccoli del vettore, si cerca il minimo della parte A[i..n] e si mette nella posizione i (aumentando così la parte ordinata). Punto di partenza: i=1 (così la parte a sinistra di A[i] è un vettore vuoto). 0: Selection-Sort(A[1..n]) 1: for i ← 1 to n − 1 do 2: k←i 3: for j ← i + 1 to n do 4: if A[k] > A[j] then 5: k←j 6: end if 7: end for 8: scambia A[i] con A[k] 9: end for 3.1 Dimostrazione della correttezza con invarianti Invariante del ciclo esterno: il sottovettore A[1..i − 1] è ordinato ∧ ∀k, l, 1 ≤ k ≤ i − 1, i ≤ l ≤ n.A[k] ≤ A[l] Inizializzazione: con i=1 la proposizione è vuota e quindi vale. Mantenimento: assumendo che il ciclo interno selezioni il minimo del A[i..n] correttamente (la discuteremo di seguito) l'invariante viene mantenuta. All'uscita: con n=1 l'invariante implica il sottovettore A[1..n − 1] è ordinato ∧ A[n − 1] ≤ A[n] e quindi il vettore è ordinato. Invariante del ciclo interno: A[k] è il minimo in A[i..j − 1] Inizializzazione: con k=i e j =i+1 è triviale. Mantenimento: come ipotesi induttiva assumiamo che l'invariante vale prima di eseguire il ciclo; il corpo del ciclo aggiorna la posizione del massimo se A[k] > A[j] e poi in ogni caso incrementa j; quindi l'invariante viene mantenuta. All'uscita: con j = n+1 l'invariante implica che A[k] è il minimo in A[i..n] e quindi il ciclo interno funziona correttamente. Quindi l'algoritmo Selection-Sort è corretto. 3.2 Tempo di esecuzione del Selection-Sort Deriviamo il tempo di esecuzione calcolando quante volte vengono eseguite le righe 1,2,3,4,5 e 8. Associamo con ognuna di queste righe un tempo di esecuzione uguale a 1 unità di tempo, cioè c1 = c2 = c3 = c4 = c5 = c8 = 1. Questa scelta non cambia in che modo il tempo di esecuzione dipende dal numero di elementi del vettore. 4 Nel caso peggiore l'indice del minimo in A[i..n] viene aggiornato ogni volta (cioè la condizione della riga 4 risulta sempre true): n−1 X n−1 X n−1 X n +n − 1+ Tcp (n) = |{z} (n − (i + 1) + 1 + 1) + (n − (i + 1) + 1) + (n − (i + 1) + 1) + n − 1 = | {z } | {z } riga 1 riga 2 i=1 | {z } i=1 | {z } i=1 | {z } riga 8 riga 3 riga 4 riga 5 n−1 X n−1 X n−1 X n +n − 1+ |{z} (n − i + 1) + (n − i) + (n − i) + n − 1 = | {z } | {z } riga 1 riga 2 i=1 | {z } i=1 | {z } i=1 | {z } riga 8 riga 3 riga 4 riga 5 n−1 X n−1 X n−1 X n +n − 1+ |{z} (i + 1) + i+ i+n − 1 | {z } | {z } riga 1 riga 2 i=1 | {z } i=1 | {z } | {z } riga 8 i=1 riga 3 riga 4 riga 5 La precedente è un polinomio di secondo grado in n. Per grandi valori di n, il tempo di esecuzione è proporzionale al quadrato del numero di elementi. Quindi nel caso peggiore l'algoritmo è quadratico. Nel caso migliore il termine associato con la riga 5 è 0 (non viene mai aggiornato la posizione del minimo). Nonostante ciò, il tempo di esecuzione, Tcm (n), è un polinomio di secondo grado in n. Quindi anche nel caso migliore l'algoritmo è quadratico. 5