1
2
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).
Quicksort
3
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 uxv.
4
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.
5
Si abbia il vettore 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. Scopro così che deve andare in
posizione 3 con alla destra i valori e alla destra .
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 2 1 9 3 8 70 1 2 3 4 5 6
2 1 3 9 8 7
6
5 2 1 9 3 8 70 1 2 3 4 5 6
VETTORE DA ORDINARE 5 2 1 9 3 8 7
5Pivot scelto
Partizione sinistra (elementi < 5) 2 1 3
Partizione destra (elementi > 5) 9 8 7
2A sinistraPivot scelto
Partizione sinistra (elementi < 2) 1
Partizione destra (elementi > 2) 3
Partizione sinistra
1 2 3
8 7
9A destraPivot scelto
Partizione sinistra (elementi < 9)
Partizione destra (elementi > 9)
Partizione destra
7 8 9
Partizione sinistra pivot partizione destra
51 2 3 7 8 9
5 2 1 9 3 8 70 1 2 3 4 5 6
0 1 2
3 2 1 9 8 7
4 5 6
1 2 8 7
2 8
0 1
s
ss
d
dd
quicksort2
8
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_partenzaSe left<pivot richiama la funzione quick(A, left , (pivot-1) ) Altrimenti quick(A,(pivot+1), right )
In pseudo codice possiamo descrivere l’algoritmo del quick-sort come segue
9
// QUICKSORT ……………………….int Hi=8;
// PROTOTIPIvoid 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 ORDINARE \n"<<endl;stampa(A, Hi);quick(A,L,R);cout<<" VETTORE ORDINATO "<<endl;stampa(A, Hi);system("pause");}
Il codice si articola in un Main e una chiamata alla procedura quick.
10
void quick (int A[], int left, int right){ int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = A[left]; while (left < right) {
while ((A[right] >= pivot) && (left <right)) right--;
if (left != right) {A[left] = A[right]; left++; } while ((A[left] <= pivot) && (left < right))
left++; if (left != right) { A[right] = A[left]; right--; } } A[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot){
quick (A, left, pivot-1);} if (right > pivot){
quick (A, pivot+1, right);}}
I°ciclo - A partire da A[right] e fino a quando:
a) left è minore di right oppure
b) se A[right]>=pivot decrementa rightSe 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 ]<=pivotd) 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_partenzaSe left<pivot richiama la funzione quick(A, left , (pivot-1) ) Altrimenti quick(A,(pivot+1), right )
11
Di seguito si riporta un esempio con un vettore di
lunghezza 12 scegliendo come pivot l’elemento
centrale.
65 21 15 99 88 79 75 87 76 46
87 76 88 84 99
84 24
24 21 15 46 79 75
15 21 76 75
88 99
87 88 84 99
15
21
21
65
24
46
46
76
7576
99
8487
84
79
88
13
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
Output del codice mostrato sull’esempio illustrato precedentemente
14
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)
15
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
16
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)
17
/* PROVA DData 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 ERICORSIONEDate 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].
*/
18
/* Date le successioni:a1=3, a2=1, a3=-1, a4=2an=a1-3*a2+a3-a4eb1=5, b2=-1, b3=3bn=-3*b1-b2+b3scrivere 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=-1an=a1-3*a2+a3*/