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]
ogni elemento di A[s…q-1] è  A[q]
ogni elemento di A[q+1…d] è > 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!)
Pseudocodice di QuickSort
Indice mediano
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)
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
Ordinamento dei
due sottoarray
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)
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
passo Divide
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)
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+1
Chiaro? Mah…
Discutiamolo in termini di invarianti di ciclo!
Partiziona: invariante di ciclo
Partiziona 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
Stabilire l’invariante
Partiziona(A,s,d)
x = A[d]
i=s-1
j=s
- L’elemento pivot è in fondo al
vettore
WHILE j < d DO
- I due sottovettori sono vuoti
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
Misurare i progressi
Partiziona(A,s,d)
x = A[d]
i=s-1
La misura di distanza è il
j=s
numero di elementi esterni ai
WHILE j < d DO
due sottovettori: cala ad
IF A[j]  x
ogni passo
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Partiziona
Mantenere l’invariante
Partiziona(A,s,d)
x = A[d]
Ogni passo aggiunge un
nuovo elemento in fondo
i=s-1
Se esso è destinato al primo
j=s
sottovettore, va scambiato
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
Condizioni di uscita
Partiziona(A,s,d)
x = A[d]
i=s-1
Al termine, l’elemento pivot
j=s
deve trovarsi fra i due
WHILE j < d DO
sottovettori
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 22
i=s-1
j=s
ij
WHILE j < d DO
A[s…i] = []
A[i+1…j-1] = []
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 22
i=s-1
j=s
i j
WHILE j < d DO
A[s…i] = [20]
A[i+1…j-1] = []
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 22
i=s-1
j=s
i j
WHILE j < d DO
A[s…i] = [20 14]
A[i+1…j-1] = []
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14]
A[i+1…j-1] = [28]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14]
IF A[j]  x
A[i+1…j-1] = [28 34]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 34 28 45 12 30 21 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15]
IF A[j]  x
A[i+1…j-1] = [34 28]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 34 28 45 12 30 21 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15]
IF A[j]  x
A[i+1…j-1] = [34 28 45]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 12 28 45 34 30 21 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15 12]
IF A[j]  x
A[i+1…j-1] = [28 45 34]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 12 28 45 34 30 21 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15 12]
IF A[j]  x
A[i+1…j-1] = [28 45 34 30]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 12 21 45 34 30 28 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15 12 21]
IF A[j]  x
A[i+1…j-1] = [45 34 30 28]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 12 21 45 34 30 28 25 16 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15 12 21]
IF A[j]  x
A[i+1…j-1] = [45 34 30 28 25]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 12 21 16 34 30 28 25 45 22
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15 12 21 16]
IF A[j]  x
A[i+1…j-1] = [34 30 28 25 45]
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)
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 15 12 21 16 22 30 28 25 45 34
i=s-1
j=s
i
j
WHILE j < d DO
A[s…i] = [20 14 15 12 21 16]
IF A[j]  x
A[i+1…j-1] = [30 28 25 45 34]
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
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 1
i=s-1
j=s
ij
WHILE j < d DO
Se un solo elemento è  pivot, ...
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
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
20 14 28 34 15 45 12 30 21 25 16 1
i=s-1
j=s
i
j
WHILE j < d DO
Se un solo elemento è  pivot,
IF A[j]  x
il THEN non viene mai eseguito
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
x
Partiziona(A,s,d)
1
2
3
4
5
6
7 8
9
10 11 12
x = A[d]
1 14 28 34 15 45 12 30 21 25 16 20
i=s-1
j=s
i
j
WHILE j < d DO
Se un solo elemento è  pivot,
IF A[j]  x
la dimensione del sottovettore sinistro è
THEN i=i+1 1, quella del sottovettore destro è n-1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Partiziona: analisi di complessità

Partiziona(A,s,d)
x = A[d]
i=s-1
 (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

 (n)
  (1)
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
20 14 28 34 15 45 12 30 21 25 16 22
s
d
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
20 14 15 12 21 16 22 30 28 25 45 34
s
q
d
QuickSort: un esempio
1
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)
1
2
3
4
5
6
7
8
9
10
q
3
4
5
6
20 14 15 12 21 16
11
12
20 14 15 12 21 16 22 30 28 25 45 34
s
2
d
QuickSort: un esempio
1
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)
1
2
3
4
5
6
7
8
9
10
d
3
4
5
6
20 14 15 12 21 16
11
12
20 14 15 12 21 16 22 30 28 25 45 34
s
2
QuickSort: un esempio
1
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)
1
2
3
4
5
6
7
8
9
10
q
d
3
4
5
6
20 14 15 12 21 16
11
12
14 15 12 16 20 21 22 30 28 25 45 34
s
2
QuickSort: un esempio
1
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)
1
2
3
4
5
6
7
8
9
10
q
d
3
14 15 12
11
12
14 15 12 16 20 21 22 30 28 25 45 34
s
2
QuickSort: un esempio
1
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)
1
2
3
4
5
6
7
8
9
10
d
3
14 15 12
11
12
14 15 12 16 20 21 22 30 28 25 45 34
s
2
QuickSort: un esempio
1
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)
1
2
3
4
5
6
7
8
9
10
d
3
12 14 15
11
12
12 14 15 16 20 21 22 30 28 25 45 34
sq
2
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
sq
d
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
ds
QuickSort: un esempio
2
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)
1
2
3
4
5
6
7
8
9
10
14 15
11
12
12 14 15 16 20 21 22 30 28 25 45 34
sq
d
3
QuickSort: un esempio
2
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)
1
2
3
4
5
6
7
8
9
10
14 15
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s
d
3
QuickSort: un esempio
2
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)
1
2
3
4
5
6
7
8
9
10
14 15
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s qd
3
QuickSort: un esempio
2
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)
1
2
3
4
5
6
7
8
9
10
14
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s qd
QuickSort: un esempio
2
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)
1
2
3
4
5
6
7
8
9
10
14
11
12
12 14 15 16 20 21 22 30 28 25 45 34
sd
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s qd
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
d s
QuickSort: un esempio
5
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)
1
2
3
4
5
6
7
8
9
10
20 21
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s
q
d
6
QuickSort: un esempio
5
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)
1
2
3
4
5
6
7
8
9
10
20 21
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s d
6
QuickSort: un esempio
5
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)
1
2
3
4
5
6
7
8
9
10
20 21
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s qd
6
QuickSort: un esempio
5
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)
1
2
3
4
5
6
7
8
9
10
20
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s qd
QuickSort: un esempio
5
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)
1
2
3
4
5
6
7
8
9
20
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
sd
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s qd
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 30 28 25 45 34
d
s
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
q
10
11
12
30 28 25 45 34
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s
9
d
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
10
11
12
30 28 25 45 34
11
12
12 14 15 16 20 21 22 30 28 25 45 34
s
9
d
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
10
11
12
30 28 25 45 34
11
12
12 14 15 16 20 21 22 30 28 25 34 45
s
9
q d
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
10
11
12
30 28 25 45 34
11
12
12 14 15 16 20 21 22 30 28 25 34 45
s
9
q d
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
d
10
30 28 25
11
12
12 14 15 16 20 21 22 30 28 25 34 45
s
9
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
d
10
25 28 30
11
12
12 14 15 16 20 21 22 25 28 30 34 45
sq
9
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
d
10
25 28 30
11
12
12 14 15 16 20 21 22 25 28 30 34 45
sq
9
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 25 28 30 34 45
d s
QuickSort: un esempio
9
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)
1
2
3
4
5
6
7
8
9
10
28 30
11
12
12 14 15 16 20 21 22 25 28 30 34 45
sq
d
10
QuickSort: un esempio
9
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)
1
2
3
4
5
6
7
8
9
10
28 30
11
12
12 14 15 16 20 21 22 25 28 30 34 45
s d
10
QuickSort: un esempio
9
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)
1
2
3
4
5
6
7
8
9
10
28 30
11
12
12 14 15 16 20 21 22 25 28 30 34 45
s qd
10
QuickSort: un esempio
9
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)
1
2
3
4
5
6
7
8
9
10
28
11
12
12 14 15 16 20 21 22 25 28 30 34 45
s qd
QuickSort: un esempio
9
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)
1
2
3
4
5
6
7
8
9
10
28
11
12
12 14 15 16 20 21 22 25 28 30 34 45
sd
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 25 28 30 34 45
s qd
QuickSort: un esempio
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)
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 25 28 30 34 45
d
s
QuickSort: un esempio
8
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)
1
2
3
4
5
6
7
8
9
10
10
11
12
25 28 30 45 34
11
12
12 14 15 16 20 21 22 25 28 30 34 45
s
9
q d
QuickSort: un esempio
12
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)
1
2
3
4
5
6
7
8
9
10
45
11
12
12 14 15 16 20 21 22 25 28 30 34 45
sd
QuickSort: un esempio
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)
Il vettore A ora è ordinato!
1
2
3
4
5
6
7
8
9
10
11
12
12 14 15 16 20 21 22 25 28 30 34 45
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
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?
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)
QuickSort: caso peggiore
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?
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)
QuickSort: caso peggiore
s
1
d
2
3
1 2
3
4
4
5
6
7
8
5
6
7 8
9
10
d
2
3
1 2
3
4
4
5
6
7
8
5
6
7 8
9
10
11
Pivot = 12
q
12
9 10 11 12
Pivot = 11
d q
s
1
12
9 10 11 12
s
1
11
2
3
1 2
3
4
4
5
6
7
8
5
6
7 8
9
10
11
12
9 10 11 12
q
Pivot = 10
…
QuickSort: caso peggiore
L’equazione di ricorrenza può essere risolta facilmente
col metodo iterativo
T(n) = T(n - 1) + (n) =
n
  ( k ) 
k 1
 n 
   k  
 k 1 
= (n2)
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-e) n e n2 = e 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)
n
=
n
(1)
(n-1)
1
n-1
((n-1)/2)
(n-1)/2
((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) + (n-1)
n
=
n
(1)
1
((n-1)/2)
(n-1)/2
((n-1)/2)
(n-1)/2
E’ la stessa complessità di una partizione bilanciata!
T(n) = (n) + (1) + (n-1) + 2T((n-1)/2)
Ma non si può garantire un comportamento così regolare!
QuickSort: caso medio?
Per ottenere un comportamento del tutto casuale, si sceglie
un 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: analisi
Consideriamo 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: analisi
Quanti 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: analisi
Quindi ogni confronto è diverso, perché cambia uno dei
due elementi
Il numero di confronti totale è in media Si<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)
Si<j pij= Sn-1i=1 Snj=i+1 2 / (j-i+1)
QuickSort randomizzata: analisi
Si<j pij= Sn-1i=1 Snj=i+1 2 / (j-i+1)
Posto k = j-i
Si<j pij= Sn-1i=1 Sn-ik=1 2 / (k+1)
< Sn-1i=1 Snk=1 2 / k <
< Sn-1i=1 log n < n log n
Si<j pij= O(n log n)