QuickSort

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

Algoritmo QuickSort

E’ un algoritmo di ordinamento sul posto

La sua complessità è• O(n2) nel caso peggiore• O(n log n) nel caso medio

Nonostante le cattive prestazioni nel caso peggiore, QuickSort è il miglior algoritmo di ordinamento in media

Struttura di QuickSortÈ un algoritmo ricorsivo basato sul Divide et Impera:

Divide: si “partiziona” il vettore A[s…d] (spostando elementi) in due sottovettori A[s…q-1] e A[q+1…d], separati da un elemento pivot A[q]

Impera: si ordinano ricorsivamente i due sottovettori A[s…q] e A[q+1…d] con QuickSort

Combina: si concatenano banalmente i sottovettori (sono già reciprocamente ordinati!)

ogni elemento di A[s…q-1] è A[q]

ogni elemento di A[q+1…d] è > A[q]

Pseudocodice di QuickSort

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q+1,d)

Indice mediano

q è l’indice che divide il vettore A in due in modo che gli elementi con indice q siano minori o uguali a quelli con indice > q

Pseudocodice di QuickSort

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

Ordinamento dei due sottoarray

Poiché il primo sottovettore ha elementi tutti minori o uguali a quelli del secondo sottovettore, basta ordinare separatamente i due sottovettori per risolvere l’intero problema

Pseudocodice di QuickSort

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

passo Divide

Partiziona è la chiave dell’algoritmo !

Partiziona

Si “partiziona” il vettore A[s…d] in due sottovettori A[s…q-1] e A[q+1…d] tali che ogni elemento di A[s…q-1] sia A[q] e ogni elemento di A[q+1…d] sia > A[q]

- si sceglie un elemento del vettore, detto pivot (perno), che farà da “spartiacque”

- si spostano gli elementi maggiori del pivot verso destra e gli elementi minori verso sinistra

L’indice mediano q dipende dall’elemento pivot:è il numero di elementi minori o uguali al pivot

Partiziona Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1Chiaro? Mah…

Discutiamolo in termini di invarianti di ciclo!

Partiziona: invariante di cicloPartiziona mantiene questo invariante di ciclo:• A[d] = x: l’elemento pivot x è in posizione terminale• il vettore A contiene

• un sottovettore A[s…i] i cui elementi sono tutti x• un sottovettore A[i+1…j-1] i cui elementi sono tutti > x

Gli stati ammissibili sono quelli in cui vale l’invariante

La distanza dallo stato finale è misurata da j

L’invariante si impone con i = s-1 e j = s

(sottovettori vuoti)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Partiziona Stabilire l’invariante

- L’elemento pivot è in fondo al vettore- I due sottovettori sono vuoti

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Partiziona

La misura di distanza è il numero di elementi esterni ai due sottovettori: cala ad ogni passo

Misurare i progressi

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Partiziona

Ogni passo aggiunge un nuovo elemento in fondoSe esso è destinato al primo sottovettore, va scambiato

Mantenere l’invariante

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Partiziona

Al termine, l’elemento pivot deve trovarsi fra i due sottovettori

Condizioni di uscita

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Esempio: partiziona(A,1,12)

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 22

i j

x

A[s…i] = []A[i+1…j-1] = []

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 22i j

x

A[s…i] = [20]A[i+1…j-1] = []

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 22

i j

x

A[s…i] = [20 14]A[i+1…j-1] = []

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 22

i j

x

A[s…i] = [20 14]A[i+1…j-1] = [28]

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 22

i j

x

A[s…i] = [20 14]A[i+1…j-1] = [28 34]

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 34 28 45 12 30 21 25 16 22

i j

A[s…i] = [20 14 15]A[i+1…j-1] = [34 28]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 34 28 45 12 30 21 25 16 22

i j

A[s…i] = [20 14 15]A[i+1…j-1] = [34 28 45]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 12 28 45 34 30 21 25 16 22

i j

A[s…i] = [20 14 15 12]A[i+1…j-1] = [28 45 34]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 12 28 45 34 30 21 25 16 22

i j

A[s…i] = [20 14 15 12]A[i+1…j-1] = [28 45 34 30]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 12 21 45 34 30 28 25 16 22

i j

A[s…i] = [20 14 15 12 21]A[i+1…j-1] = [45 34 30 28]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 12 21 45 34 30 28 25 16 22

i j

A[s…i] = [20 14 15 12 21]A[i+1…j-1] = [45 34 30 28 25]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 12 21 16 34 30 28 25 45 22

i j

A[s…i] = [20 14 15 12 21 16]A[i+1…j-1] = [34 30 28 25 45]

x

Esempio: partiziona(A,1,12)

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 15 12 21 16 22 30 28 25 45 34

i j

A[s…i] = [20 14 15 12 21 16]A[i+1…j-1] = [30 28 25 45 34]

x

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Partiziona: un caso limite

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 1

i j

x

Se un solo elemento è pivot, ...

Partiziona: un caso limitePartiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 1

i j

Se un solo elemento è pivot, il THEN non viene mai eseguito

x

Partiziona: un caso limite Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

1 2 3 4 5 6 7 8 9 10 11 12

1 14 28 34 15 45 12 30 21 25 16 20

i jSe un solo elemento è pivot, la dimensione del sottovettore sinistro è 1, quella del sottovettore destro è n-1

x

Partiziona(A,s,d)

x = A[d]

i = s - 1

j = s

WHILE j < d DO

IF A[j] x

THEN i=i+1

“scambia A[i] con A[j]”

j = j+1

“scambia A[i+1] con A[d]”

RETURN i+1

Partiziona: analisi di complessità

)(1

)1(

)(n

QuickSort: un esempio

1 2 3 4 5 6 7 8 9 10 11 12

20 14 28 34 15 45 12 30 21 25 16 22s d

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q)

Quick-Sort(A,q + 1,d)

QuickSort: un esempio

1 2 3 4 5 6 7 8 9 10 11 12

s d

20 14 15 12 21 16 22 30 28 25 45 34

q

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6

20 14 15 12 21 16

1 2 3 4 5 6 7 8 9 10 11 12

s d

20 14 15 12 21 16 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

20 14 15 12 21 16 22 30 28 25 45 34

1 2 3 4 5 6

20 14 15 12 21 16

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

14 15 12 16 20 21 22 30 28 25 45 34

q

1 2 3 4 5 6

20 14 15 12 21 16

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

14 15 12 16 20 21 22 30 28 25 45 34

1 2 3

14 15 12

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

14 15 12 16 20 21 22 30 28 25 45 34

1 2 3

14 15 12

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

1 2 3

12 14 15

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34q

2 3

14 15

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

2 3

14 15

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

2 3

14 15

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

2

14

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

2

14

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

5 6

20 21

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

5 6

20 21

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

5 6

20 21

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

5

20

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q)

Quick-Sort(A,q + 1,d)

5

20

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10 11 12

30 28 25 45 34

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10 11 12

30 28 25 45 34

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 45 34

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10 11 12

30 28 25 45 34

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10 11 12

30 28 25 45 34

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 30 28 25 34 45

8 9 10

30 28 25

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10

25 28 30

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10

25 28 30

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 25 28 30 34 45

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

9 10

28 30

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

9 10

28 30

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

9 10

28 30

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

9

28

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

9

28

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 25 28 30 34 45

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 25 28 30 34 45

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

8 9 10 11 12

25 28 30 45 34

1 2 3 4 5 6 7 8 9 10 11 12

s d

12 14 15 16 20 21 22 25 28 30 34 45

q

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

12

45

1 2 3 4 5 6 7 8 9 10 11 12

sd

12 14 15 16 20 21 22 25 28 30 34 45

QuickSort: un esempioQuick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

1 2 3 4 5 6 7 8 9 10 11 12

12 14 15 16 20 21 22 25 28 30 34 45

Il vettore A ora è ordinato!

QuickSort: analisi di complessità

Il tempo di esecuzione di QuickSort dipende dal bilanciamento fra i sottovettori costruiti da Partiziona

• Il caso migliore si verifica quando i sottovettori sono perfettamente bilanciati, entrambi di dimensione n/2

• Il caso peggiore si verifica quando un sottovettore è sempre di dimensione 1 (l’altro è quindi di dimensione n - 1)

QuickSort: caso migliore

Se i sottovettori sono di uguale dimensione:

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

per il caso 2 del teorema principale:

T(n) = (n log n)

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

Quando si verifica il caso migliore?

QuickSort: caso peggiore

Il sottovettore sinistro ha dimensione 1, quello destro dimensione n - 1:

T(n) = T(1) + T(n - 1) + (n)

Poiché T(1) = 1 otteniamo

T(n) = T(n - 1) + (n)

Quick-Sort(A,s,d)

IF s < d

THEN q = Partiziona(A,s,d)

Quick-Sort(A,s,q-1)

Quick-Sort(A,q + 1,d)

Quando si verifica il caso peggiore?

QuickSort: caso peggiore

q

s d

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

Pivot = 12

q

s d

Pivot = 11

q

s d

Pivot = 10

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

…

QuickSort: caso peggiore

L’equazione di ricorrenza può essere risolta facilmente col metodo iterativo

T(n) = T(n - 1) + (n) =

= (n2)

n

kk

1)(

n

kk

1

QuickSort: caso medio?

La complessità di QuickSort nel caso medio è molto vicina a quella del caso migliore

Per averne un’intuitizione, supponiamo che ad ogni passo Partiziona dia due sottovettori molto sbilanciati, ma con un rapporto fisso

n1 = 99/100 n n2 = n/100

Allora

T(n) = T(99n/100) + T(n/100) + (n) = (n log n)

(basta applicare il metodo iterativo…)

QuickSort: caso medio?La stessa cosa vale per qualsiasi rapporto fisso fra le

dimensioni dei sottovettori

Se n1 = (1-) n e n2 = n, allora T(n) = (n log n)

Ma non si può garantire un comportamento così regolare!

Occorre invece un’ipotesi sulla distribuzione di probabilità delle diverse istanze, ad esempio che ogni permutazione sia equiprobabile

Per ogni istanza, la partizione sarà “buona” in alcuni livelli, “cattiva” in altri

QuickSort: caso medio?Facciamo un’altra ipotesi intuitiva: Partiziona genera

una suddivisione cattiva e una buona, alternate

n

1 n-1

(n-1)/2

n=

(n-1)/2

(n)

(1) (n-1)

((n-1)/2) ((n-1)/2)

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

QuickSort: caso medio?Facciamo un’altra ipotesi intuitiva: Partiziona genera

una suddivisione cattiva e una buona, alternate

n

1 (n-1)/2

n=

(n-1)/2

(n) + (n-1)

(1) ((n-1)/2) ((n-1)/2)

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

E’ la stessa complessità di una partizione bilanciata!

Ma non si può garantire un comportamento così regolare!

QuickSort: caso medio?Per ottenere un comportamento del tutto casuale, si sceglieun elemento pivot casuale anziché l’ultimo del vettore A

RandomPartiziona(A,s,d)

p = random(s,d)

“scambia A[p] e A[d]”

Partiziona(A,s,d)

Questo rende improbabile che la partizione sia sempre sbilanciata, anche per le istanze quasi ordinate

QuickSort randomizzata: analisiConsideriamo tutto l’albero delle chiamate di QuickSort

Ogni chiamata comporta• alcune operazioni O(1)• una chiamata a Partiziona, che a sua volta comporta

– altre operazioni O(1)– un ciclo di confronti fra gli elementi del sottovettore e il pivot;

Ogni chiamata ha un pivot diverso: avvengono al più n chiamate

La complessità è O(n) + la complessità dei cicli di confronti

QuickSort randomizzata: analisiQuanti confronti fra A[j] e x avvengono?

Sia ai l’i-esimo numero in ordine crescente e pij la probabilità complessiva che durante l’algoritmo si confrontino ai e aj

Inizialmente, ai e aj fanno parte del vettore corrente.

Se in qualsiasi momento viene scelto come pivot un elemento intermedio, ai e aj finiscono in sottovettori diversi e non verranno mai confrontati

Se viene scelto come pivot uno dei due, ai e aj vengono confrontati esattamente una volta

QuickSort randomizzata: analisiQuindi ogni confronto è diverso, perché cambia uno dei due elementi

Il numero di confronti totale è in media i<j pij

pij è la probabilità che in un vettore contenente sia ai sia aj si scelga come pivot o ai o aj, ma non un elemento intermedio

pij = 2 / (j-i+1)

i<j pij= n-1i=1 n

j=i+1 2 / (j-i+1)

QuickSort randomizzata: analisi

i<j pij= n-1i=1 n

j=i+1 2 / (j-i+1)

Posto k = j-i

i<j pij= n-1i=1 n-i

k=1 2 / (k+1) < n-1

i=1 nk=1 2 / k <

< n-1i=1 log n < n log n

i<j pij= O(n log n)