Pagine

08 settembre 2011

Quicksort

Ciao gente,
da quanto tempo! Come state? Io benone :-)
Da qualche giorno ho iniziato a seguire il corso di algoritmi del MIT, molto bello.
Il corso è fruibile sul loro sito su cui sono presenti le videolezioni, le trascrizioni, appunti, ecc...
Ora... Invogliato da questo corso di algoritmi ho deciso di togliermi dalla scarpa un sassolino che avevo sin dai tempi dell'università ovvero capire il misterioso quicksort.
Lo so, sarò una zappa io, però mi ha sempre messo in difficoltà :-/
Comunque l'altra mattina in un momento di calma in ufficio ho deciso di dedicarmici e sono riuscito al primo tentativo :-)
 

Ovviamente questa implementazione è più lenta del sorted() della libreria standard che: a) Non sono sicuro sia un quicksort b) Probabilmente è fatta in C e compilata. In ogni caso è stato un bell'esercizio e comunque è anche molto molto comprensibile come codice :-) Ma come funziona? Se la lunghezza di V è 1 o 0 vuol dire che il vettore è già ordinato. altrimenti: Inizializziamo 3 sottovettori: V1 contiene gli elementi minori del pivot, V2 contiene gli elementi maggiori del pivot e Z contiene l'elemento pivot e quelli a lui uguali. L'elemento pivot è p che ho preso come ultimo elemento della lista. Ora il ciclo for smista gli elementi tra le tre liste e la funzione viene richiamata ricorsivamente sulle sotto liste. Alla fine le 3 liste ordinate vengono concatenate assieme dall'istruzione return A1+Z+A2. Chiaro no? :-) Saluti a tutti!

Nessun commento:

Posta un commento