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.
È 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 (segue)
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.
Quicksort (segue)
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.
Quicksort (segue)
Quicksort (segue)
Di seguito si riporta un esempio con un vettore di lunghezza 12 scegliendo come pivot l’elemento centrale.
Quicksort (segue)
Quicksort (segue)
In pseudo codice possiamo descrivere l’algoritmo del quick-sort come segue
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 usciamo 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.
I° ciclo
2° ciclo
Quicksort (segue)
Il codice si articola in un Main e una chiamata alla procedura quick.
Mostra codiceQuicksort (segue)
Mostra codiceQuicksort (segue)
Mostra codiceQuicksort (segue)
Un esempio di output del codice mostrato precedentemente.
Quicksort (segue)
Output del codice mostrato sull'esempio illustrato precedentemente.
Quicksort (segue)
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).
Esercizio
Scrivere un algoritmo ricorsivo per la funzione booleana che ricerca in una matrice N×M se nelle righe pari sono riportati solo numeri pari e nelle righe dispari solo numeri dispari.
Esempio.
Esercizio
Scrivere una funzione ricorsiva che, dati in ingresso una cifra c ed un numero intero positivo n, restituisca il numero di volte in cui c occorre in n.
Esempio: se c=1 e n=21510 la funzione deve restituire 2
Mostra codiceEsercizio
Date due successioni an=….., bn=……., scrivere una funzione ricorsiva che dica se nei primi N termini an e bn assumono almeno una volta lo stesso valore.
