Soluzione 6: Algoritmo Quicksort Si basa sulla partizione dell’array rispetto ad un suo elemento scelto come “pivot”. L’operazione viene quindi ripetuta sulle due parti così ottenute. 1 2 3 4 5 6 7 8 9 10 11 12 09 46 290 48 364 192 57 84 63 7 91 75 i ji i ji ij ji ji j j j j j j Quicksort(A,p,r) non ordinati A if p < r q = Partition(A,p,r) 1 p 1 p 1 1 r n q r n p q r n p q r n r n A Quicksort(A,p,q-1) A Quicksort(A,q+1,r) A ordinati A 1 p Partition(A,p,r) x = A[r] i = p -1 A 1 p r x r A 1 for j = p to r -1 i p 1 p i j 1 p i 1 n r p 1 p i T (n) bn a (n) P n r n r n x A return i+1 r x A scambia A[i+1] e A[r] n x A if A[j] < x i = i+1 scambia A[i] e A[j] n Quicksort (A,p,r) // Complessità massima if p < r q = Partition(A,p,r) Quicksort(A,p,q-1) n r p 1 Quicksort(A,q+1,r) Array ordinato o ordinato in senso inverso QS max T se n 1 c ( n) QS QS bn a Tmax (n 1) Tmax (0) se n 1 QS max T (n) bn a c T QS max T QS max ( n ) ( n ) 2 (n 1) Quicksort(A,p,r) // Complessità minima if p < r // q = Partition(A,p,r) // n r p 1 c P T (n) QS T Quicksort(A,p,q-1) // min ( ( n 1) / 2) QS T Quicksort(A,q+1,r) // min ( ( n 1) / 2) QS min T se n 1 c ( n) P QS c T (n) 2Tmin ( n / 2) se n 1 T (n) O(n log n) QS min Quicksort (A,p,r) // Complessità media if p < r then q = Partition(A,p,r) Quicksort(A,p,q-1) Quicksort(A,q+1,r) n r p 1 c QS 1 r Tmed ( n) QS QS bn a q p [Tmed (q p) Tmed (r q)] n c 1 n1 QS 1 n1 QS bn a j 0 Tmed ( j ) j 0 Tmed ( j ) n n c se n 1 2 n 1 QS bn a j 0 Tmed ( j ) se n 1 n QS med T (n) O(n log n) se n 1 se n 1 se n 1 se n 1 QS med Per n > 1 T 2 n 1 QS (n) bn a i 0 Tmed (i ) n e moltiplicando per n otteniamo n 1 QS 2 QS nTmed (n) bn an 2 j 0 Tmed ( j ) QS T Per n = 2 med ( 2) 2b a 2c Per n > 2 QS med nT (n) (n 1)T QS med (n 1) QS 2Tmed (n 1) (2n 1)b a e dunque QS QS nTmed (n) (n 1)Tmed (n 1) (2n 1)b a QS QS nTmed (n) (n 1)Tmed (n 1) (2n 1)b a dividendo per n(n+1) 1 1 QS (2n 1)b a QS Tmed (n) Tmed (n 1) n 1 n n(n 1) 1 QS ponendo f (n) Tmed (n) otteniamo n 1 (2n 1)b a f (n) f (n 1) per n 2 n(n 1) f (2) (2b a 2c) / 3 c1 f (2) (2b a 2c) / 3 c1 (2n 1)b a f (n) f (n 1) per n 2 n(n 1) la cui soluzione è (2 j 1)b a f (n) f (2) j 3 j ( j 1) (2 j 2)(b a ) n c1 j 3 j ( j 1) 1 n c1 c2 j 3 j n 1 c1 c2 dx c1 c2 (ln n ln 2) 2 x n Infine QS Tmed (n) (n 1) f (n) (n 1)c1 c2 (ln n ln 2) O(n log n) Quindi QS med T (n) O(n log n) La complessità media O(n log n) di Quick-Sort vale soltanto se tutte le permutazioni dell’array in ingresso sono ugualmente probabili. In molte applicazioni pratiche questo non è vero!!! Vi sono applicazioni in cui le permutazioni quasi ordinate sono molto più probabili e questo può aumentare la complessità media fino ad O(n2). Randomized-Partition(A,p,r) i = Random(p,r) scambia A[i] e A[r] return Partition(A,p,r) Randomized-Quicksort(A,p,r) if p < r then q = Randomized-Partition(A,p,r) Randomized-Quicksort(A,p,q-1) Randomized-Quicksort(A,q+1,r)