Quickselect 8 Maggio 2008
Posted by fripp in Algoritmi, C, C++, Debian, GNU/Linux, Informatica, Java, Mac OS X, Matematica, Ordinamento, Programmazione, Quickselect, Quicksort, Selezione, Sistemi Operativi, Unix.Tags: partizionamento, pivot, Quickselect, selection, Selezione, statistiche d'ordine
add a comment
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 
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 in C di questo algoritmo:
(continua…)
