Quickselect

Maggio 8, 2008 | By Calogero In C, Debian, Informatica, Mac OS X, Unix, frammenti di razionalitÃ , gnu/linux, java, programmazione, sistemi operativi |
FONTE: http://fripp.wordpress.com
E' LA TUA PRIMA VOLTA SU "IL BLOGGATORE"? SEGUI GRATIS I NOSTRI FEEDS!

Il Quickselect è un algoritmo randomizzato ricorsivo che trova l’elemento che si troverebbe in k-esima posizione se l’array in cui si trova fosse ordinato.

Su un array di grandezza $n$ l’algoritmo esegue $O(n^2)$ confronti nel caso peggiore e $O(n)$ nel caso atteso. Si basa sull’algoritmo Quicksort.

L’idea di base che sta alla base dell’algoritmo è molto semplice: se si deve estrarre l’elemento che si troverebbe in k-esima posizione se l’array fosse ordinato, basta ordinare di volta in volta la porzione dell’array in cui l’elemento si troverebbe, trascurando il resto dell’array.

Ecco un’implementazione...

Leggi il seguito »