1
Quicksort
Quicksort è un algoritmo di ordinamento ricorsivo che si basa sul
paradigma "divide et impera“ come il merge sort.
La base del suo funzionamento è l'utilizzo ricorsivo della seguente
procedura :
preso un elemento (pivot) da una struttura dati (es. array) si
pongono gli elementi più piccoli rispetto al pivot a sinistra e gli
elementi più grandi a destra.
Il Quicksort, è l'algoritmo di ordinamento che ha, in generale,
prestazioni migliori tra quelli basati su confronto.
E' stato ideato da Charles Antony Richard Hoare nel 1960 ed ha
una complessità media di O(n*log2n) ma nel caso peggiore di
O(n2).
2
Nel quicksort la ricorsione viene fatta non dividendo il vettore
in base agli indici ma in base al suo contenuto.
Se il vettore ha un solo elemento è banalmente ordinato;
altrimenti si sceglie come pivot un elemento in maniera casuale
(quello centrale o il primo in genere) e si scandisce il vettore da
ordinare a partire dalle due estremità, scambiando le coppie
u,v che non soddisfano la relazione uxv.
3
Quando gli indici si incontrano si è partizionato il vettore in
due sottovettori tali che tutti gli elementi del primo sono non
maggiori del pivot e tutti gli elementi del secondo sono non
minori di esso.
Applicando ricorsivamente l’algoritmo ai due sottovettori si
ordina l’intero vettore.
Di seguito si riporta un esempio di funzionamento per un
vettore di lunghezza 7 scegliendo come pivot il primo elemento.
4
0
Si abbia il vettore
1
2
3
4
5
6
5 2 1 9 3 8 7
scelgo un pivot, esempio
5 e mi chiedo quale deve essere la sua collocazione finale nel vettore
ordinato? Evidentemente quando avrà alla sua sinistra tutti valori minori
e alla sua destra tutti valori maggiori.
posizione 3 con alla destra i valori
Scopro così che deve andare in
2 1 3
e alla destra 9
8 7 .
Prendo ora il sottovettore a sinistra e scelgo un nuovo pivot, ad esempio
2 e trovo la sua collocazione in questo sottovettore. Esso va messo
nella posizione 1 con a sinistra 1 e a destra 3. Ora gli indici che
percorrono il vettore si sovrappongono e posso passare a analizzare il
sottovettore alla destra di 5. Scelgo come pivot 9. In questo caso parto
da destra e verifico che 7 è < 9 quindi scrivo 7 nella posizione del 9,
trovo poi 8<9 e lo metto subito dopo il 7 cioè dove si trova e quindi
essendo gli indici sovrapposti scrivo 9 nella posizione 6. Non essendoci
altri sottovettori il processo è terminato.
5
0
1
2
3
4
5
6
VETTORE DA ORDINARE
5 2 1 9 3 8 7
5 2 1 9 3 8 7
Pivot scelto 5
Partizione sinistra (elementi < 5)
2 1 3
Partizione destra (elementi > 5)
9 8 7
A sinistra
Pivot scelto
2
Partizione sinistra (elementi < 2)
1
Partizione sinistra
Partizione destra (elementi > 2)
3
1 2 3
A destra
Pivot scelto
9
Partizione sinistra (elementi < 9)
8 7
Partizione destra (elementi > 9)
Partizione destra
7 8 9
Partizione sinistra pivot partizione destra
1 2 3
5
7 8 9
6
5 2 1 9 3 8 7
0
s
1
2
3
4
5
6
d
3 2 1
0
s
1 2
1
9 8 7
2
s
4
5
6
8 7
0
d
2
1
d
8
quicksort2
In pseudo codice possiamo descrivere l’algoritmo del quick-sort come segue
quick(A, left, right)
Poni left_di_partenza=left;
right_di_partenza=right
Pivot=A[left]
I°ciclo - A partire da A[right] e fino a
quando:
a) left è minore di right oppure
b) se A[right]>=pivot
decrementa right
Se si esce per la condizione b)
poniamo A[left]=A[right] e
incrementa left.
Comunque passa al ciclo successivo.
II°ciclo - Fino a quando:
c)
A[left ]<=pivot
d)
left < right
incrementa left
Se usciamo per la condizione d)
poniamo A[right]=A[left] e
decrementa right.
Comunque vai al passo successivo.
Poni A[left ]=pivot
pivot=left
left=left_di_partenza
right=right_di_partenza
Se left<pivot richiama la funzione
quick(A, left , (pivot-1) )
8
Altrimenti quick(A,(pivot+1), right )
Il codice si articola in un Main e una chiamata alla procedura quick.
// QUICKSORT
……………………….
int Hi=8;
// PROTOTIPI
void q_sort(int [], int , int );
void stampa(int [],int );
// ******** MAIN *******
int main()
{
int L=0;
int R=6;
Hi=6;
int A[7]={5,2,1,9,3,8,7};
cout<<"
VETTORE DA
stampa(A, Hi);
quick(A,L,R);
cout<<"
VETTORE
stampa(A, Hi);
system("pause");
}
ORDINARE \n"<<endl;
ORDINATO "<<endl;
9
void quick (int A[], int left, int right)
{ int pivot, l_hold, r_hold;
I°ciclo - A partire da A[right] e fino a quando:
l_hold = left;
r_hold = right;
a) left è minore di right oppure
pivot = A[left];
while (left < right)
b) se A[right]>=pivot
{
decrementa right
while ((A[right] >= pivot) && (left <right)) Se si esce per la condizione b)
poniamo A[left]=A[right] e
right--;
incrementa left.
if (left != right)
{A[left] = A[right];
Comunque passa al ciclo successivo.
left++; }
while ((A[left] <= pivot) && (left < right))
II°ciclo - Fino a quando:
left++;
c) A[left ]<=pivot
if (left != right)
d) left < right
{ A[right] = A[left];
incrementa left
right--; }
Se usciamo per la condizione d)
}
poniamo A[right]=A[left] e
A[left] = pivot;
decrementa right.
pivot = left;
Comunque vai al passo successivo.
left = l_hold;
right = r_hold;
Poni A[left ]=pivot
if (left < pivot){
pivot=left
quick (A, left, pivot-1);}
left=left_di_partenza
right=right_di_partenza
if (right > pivot){
Se left<pivot richiama la funzione
quick (A, pivot+1, right);}
10
quick(A, left , (pivot-1) )
}
Altrimenti quick(A,(pivot+1), right )
Di seguito si riporta un esempio con un vettore di
lunghezza 12 scegliendo come pivot l’elemento
centrale.
11
65
21
15
99
88
79
75
87
76
46
84
24
75
87
65
24
21
15
46
79
24
15
21
46
21
21
88
84
99
79
46
15
76
76
75
87
75
88
84
99
87
84
76
88
76
84
99
88
99
Output del codice mostrato sull’esempio illustrato precedentemente
VETTORE DA ORDINARE
65 21 15 99 88 79 75 87 76 46 84 24
richiamo q_sort sull'intervallo 0-11
Parto con pivot 65 left= 0 right= 11
65 21 15 99 88 79 75 87 76 46 84 24
richiamo q_sort sull'intervallo 0-3
Parto con pivot 24 left= 0 right= 3
24 21 15 46 65 79 75 87 76 88 84 99
richiamo q_sort sull'intervallo 0-1
Parto con pivot 15 left= 0 right= 1
15 21 24 46 65 79 75 87 76 88 84 99
richiamo q_sort sull'intervallo 1-1
Parto con pivot 21 left= 1 right= 1
15 21 24 46 65 79 75 87 76 88 84 99
richiamo q_sort sull'intervallo 3-3
Parto con pivot 46 left= 3 right= 3
15 21 24 46 65 79 75 87 76 88 84 99
richiamo q_sort sull'intervallo 5-11
Parto con pivot 79 left= 5 right= 11
15 21 24 46 65 79 75 87 76 88 84 99
richiamo q_sort sull'intervallo 5-6
Parto con pivot 76 left= 5 right= 6
15 21 24 46 65 76 75 79 87 88 84 99
richiamo q_sort sull'intervallo 5-5
Parto con pivot 75 left= 5 right= 5
15 21 24 46 65 75 76 79 87 88 84 99
richiamo q_sort sull'intervallo 8-11
Parto con pivot 87 left= 8 right= 11
15 21 24 46 65 75 76 79 87 88 84 99
richiamo q_sort sull'intervallo 8-8
Parto con pivot 84 left= 8 right= 8
15 21 24 46 65 75 76 79 84 87 88 99
richiamo q_sort sull'intervallo 10-11
Parto con pivot 88 left= 10 right= 11
15 21 24 46 65 75 76 79 84 87 88 99
richiamo q_sort sull'intervallo 11-11
Parto con pivot 99 left= 11 right= 11
15 21 24 46 65 75 76 79 84 87 88 99
VETTORE ORDINATO
15 21 24 46 65 75 76 79 84 87 88 99
13
Ricordarsi che nella ricorsione l’ordine con cui le istruzioni
vengono eseguite, cioè se prima o dopo la chiamata ricorsiva, è
fondamentale.
Quindi:
A-
se una o più istruzioni riducono la dimensione del
problema esse devono precedere la chiamata ricorsiva
(vedi quick sort)
B-
se una o più istruzioni necessitano del risultato della
ricorsione vanno poste dopo la chiamata ricorsiva
(vedi merge sort)
14
ESERCIZIO
Data una matrice quadrata A di interi, percorrendo la
quale da sinistra a destra e dall'alto in basso si
trovano tutti valori crescenti. Utilizzando l'algoritmo di
ricerca binaria verificare che un preassegnato k
appartiene alla diagonale principale fornendone le
coordinate .
Es. Verificare se 36 soddisfa la richiesta
2
3
5
7
9
11
14
21
23
34
36
39
41
43
45
49
15
Fornire una funzione ricorsiva tale che assegnato un
vettore ordinato di numeri interi dica quanti e quali dei
numeri in essa contenuti sono numeri di Fibonacci.
Es.
L1=[1,3,7,11,13, 19, 21, 33, 34]
I numeri di Fibonacci presenti nella lista sono 6 (1, 3,
13, 21, 34)
16
/* PROVA D
Data una matrice MxM, con M dispari e un vettore A[N] scrivere
una funzione ricorsiva che conti quanti elementi appartenenti
alla cornice esterna(vedi esempio) appartengono anche al
vettore A.
*/
/* PROVA E
RICORSIONE
Date due matrici A e B (MxM) determinare la matrice C, con
una procedura ricorsiva, in cui se A[i][j]=B[j][i] allora
C[i][j]=0, altrimenti vale A[i][j]+B[j][i].
*/
17
/*
Date le successioni:
a1=3, a2=1, a3=-1, a4=2
an=a1-3*a2+a3-a4
e
b1=5, b2=-1, b3=3
bn=-3*b1-b2+b3
scrivere una funzione ricorsiva che fornisca la somma di tutti i termini
maggiori di 0 prodotti dalle due successioni per un assegnato N.
*/
/*
Scrivere una procedura ricorsiva che riempia un vettore A di
lunghezza N a partire dalla fine con i primi N termini prodotti dalla
successione
a1=3, a2=1, a3=-1
an=a1-3*a2+a3
*/
18