Ciao a tutti,oggi parliamo del quick sort altro algoritmo di ordinamento. E un algoritmo sul posto che prende in input una sequenza di elementi e produce una sequenza ordinata in output. Di solito si usa l’array come struttura dati della sequenza.
Anche quick sort usa il metodo divide e impera. Per ordinare gli elementi un array A[p..r] con quick sort si procede cosi:
Il punto fondamentale nel quick sort è capire come si fa a dividere un array in modo che ogni elemento del primo sotto array sia inferiore o uguale ad ogni elemento del secondo sotto array. Quicksort usa una procedura per farlo:
Partizione.
Analisi di partizione:
Questo è lo pseudo codice:
Domanda: ma questo algoritmo cosa fa nel dettaglio?
Per capirlo andiamo a dimostrarne la correttezza con l’invariante di ciclo.
Correttezza di partizione:
l’invariante di ciclo
1.Prima del ciclo
Le righe 2 e 3 formano 2 sotto vettori A[p..p-1] (A[p..i]) e A[p..p-1] (A[i+1..j-1]) vuoti.
Quindi l’invariante è rispettato.
2.Durante il ciclo
Il ciclo score l’array A[p..r-1] con l’indice j e secondo il caso di figura ,mette l’elemento incontrato nel sotto vettore giusto:
-Le righe 5,6,7 si assicurano che ogni volta che abbiamo un elemento piu piccolo del pivot x (riga 5),questo ultimo viene aggiunto al sotto vettore A[p..i] (la riga 6 aumenta di 1 la dimensione del sotto vettore e la riga 7 mette l’elemento A[j] nel sotto vettore giusto).
-Se invece l’elemento A[j] è maggiore del pivot x, non si fa niente perché la riga 8 li mette automaticamente nel sotto vettore giusto cioè A[i+1..j-1].
-La riga 8 serve a scorrere nel vettore A[j..r] con gli elementi che non sono ancora stati inseriti dentro i sotto vettori. L’incremento della riga 8 mette tutti gli elementi che non sono stati cambiati dalla riga 7 (perché magiori del pivot) dentro il sotto vettore A[i+1..j-1].
Quindi anche cui l’invariante di ciclo viene rispettato.
3.Dopo il ciclo
Alla fine j = r il che significa che il sotto vettore A[i+1..j-1] si ferma a r-1 prima del pivot A[r]. La riga 9 scambia il primo elemento di A[i+1..j-1] con A[r],il che significa che cambia questo sotto vettore in A[i+2..r].
Quindi l’invariante è rispettato e l’array è partizionato con il pivot in A[i+1]. da cui si capisce naturalmente la riga 10.
Tempo di esecuzione:
righe 1,2,3,9 e 10 impiegano un tempo costante.
il ciclo fa n-1 confronti quindi impiega :
Analisi di QuickSort
pseudocodice:
La valutazione delle prestazioni del QuickSort dipende dal bilanciamento dei sotto vettori costruito da partizione(). vediamo qualche caso di figura:
1. Caso peggiore:
2.Caso Migliore
La partizione si divide esattamente a metà ogni volta,allora si usa il teorema fondamentale.:
3.Caso 1/10:9/10
Grazie di aver letto l’articolo. Dubbi ,domande e suggerimenti ?Lo spazio per i commenti è qui sotto.