Quick Sort

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.