1. 2 Quicksort è un algoritmo di ordinamento ricorsivo che si basa sul paradigma "divide et impera...

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

D:\programmazione II 2011b\ricorsione\qsortfin2.cpp

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 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

C:\Users\Ernesto Burattini\Desktop\programmazione II 2011b\ricorsione\qsortfin.cpp

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

C:\Users\Ernesto Burattini\Desktop\programmazione II 2011b\ricorsione\diagonale_matrici.cpp

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].

*/

C:\Users\Ernesto Burattini\Desktop\programmazione II 2011b\ricorsione\matrice provaD.cpp

C:\Users\Ernesto Burattini\Desktop\programmazione II 2011b\ricorsione\matrice provaE.cpp

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*/

C:\Users\Ernesto Burattini\Desktop\programmazione II 2011b\ricorsione\successioni prova B.cpp

C:\Users\Ernesto Burattini\Desktop\programmazione II 2011b\ricorsione\successioni prova A.cpp

1. 2 Quicksort è un algoritmo di ordinamento ricorsivo che si basa sul paradigma "divide et impera...

Documents

Transcript of 1. 2 Quicksort è un algoritmo di ordinamento ricorsivo che si basa sul paradigma "divide et impera...