Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 11.Quicksort


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

I° ciclo

2° ciclo

2° ciclo


Quicksort (segue)

Il codice si articola in un Main e una chiamata alla procedura quick.

Mostra codice

Quicksort (segue)

Mostra codice

Quicksort (segue)

Mostra codice

Quicksort (segue)

Mostra codice Mostra codice

Allegato: Mostra codice

Quicksort (segue)

Un esempio di output del codice mostrato precedentemente.

Un esempio di output del codice mostrato precedentemente.


Quicksort (segue)

Output del codice mostrato sull’esempio illustrato precedentemente.

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.

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 codice

Esercizio

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.

I materiali di supporto della lezione

Allegati lezione 11

qsortfin.cpp

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion