Esercizi di programmazione in Pascal->Quicksort

Quicksort

In questo piccolo tutorial verrà spiegato l'implementazione del classico ordinamento Quicksort.
Questo algoritmo è molto famoso perchè nel caso medio ha una complessità di o(nlogn), è di facile implementazione ed è il più utilizzato.
Dato un vettore di elementi da ordinare, l'algoritmo si basa sul partizionamento ricorsivo del vettore in due sotto-vettori in modo che ogni elemento del primo vettore è più piccolo di ogni elemento del secondo. La procedura di ripartizione consiste nello scegliere un elemento x del vettore (detto perno) e nel costruire mediante degli scambi un vettore dove tutti gli elementi più piccoli sono a sinistra di x e tuti gli elementi più grandi a destra.

Di seguito la definizione del vettore da ordinare e la variabile contenete il vettore:
La funzione seguente esegue la ripartizione del sottovettore di A nell'intervallo [p,r]. Viene scelto il primo elemento come perno, cioè A[p]. La scansione avviene mediante due indici ("i" e "j") che iniziano rispettivamente all'inizio e alla fine del sotto vettore. Nel ciclo principale (cioè il while) viene dapprima eseguita una scansione per trovare l'elemento A[i] a sinistra di x più grande di x, poi una scansione per trovare l'elemento A[j] a destra di x più piccolo di x. Quindi A[i] e A[j] vengono scambiati. La scansione termina quando "i" e "j" si incontrano. Il valore "i" ed "j" rappresentano quindi il punto dove è possibile dividere il vettore cioè A[p, j] e A[j,r]. Si noti che "j" nel caso migliore si trova in (r-p)/2 e nel caso peggiore corrisponde a p o ad r. Si noti che un vettore ordinato corrisponde al caso peggiore. La funzione restituisce il valore "j" calcolato.

Vediamo il codice:

La procedura seguente esegue l'ordinamento del sottovettore di A nell'intervallo [p,r]. Possiamo notare come viene implementato il passo ricorsivo. Dapprima viene richiamata la funzione di ripartizione del vettore vista precedentemente, quindi otteniamo un indice "q" con il quale possiamo suddividere il sottovettore vettore A[p,r] in altri due sottovettori A[p,q] e A[q+1,r]. Si noti che per la proprietà del partizionamento alla fine della ricorsione il vettore risulta completamente ordinato.
Vediamo il codice:
Da notare che la prima chiamata alla proedura ordina() deve corrisponde a tutto il vettore, quindi all'intervalo [1, n] di A.
Vediamo il codice:

Il corpo del programma crea un vettore con numeri generati casualmente, richiama la procedura di ordinamento e quindi stampa il risultato.
Vediamo di seguito il codice.
Ci sono diverse varianti alla scelta del perno nel partizionamento. Invece di prendere il primo elemento, ad esempio può essere preso a caso nel vettore A[p,r]. In questo modo se A è già ordinato è molto improbabile incorrere nel caso peggiore.
Nella seguente funzione vediamo come viene calcolato il perno e sostituito al primo elemento. La funzione quindi può richiamare la funzione Partizione():
Ovviamente la funzione ordina() deve essere anche modificata:


Scarica sorgenti (1 Kb)