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
trackback
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:
inline int partition(int *v, int i, int f){
int x=v[i];
int inf=i;
int sup=f+1;
while(1){
do
inf++;
while(v[inf]<=x && inf<=f);
do
sup--;
while(v[sup]>x);
if(inf<sup)
swap(v+inf,v+sup);
else
break;
}
swap(v+i,v+sup);
inf=i;
int s=sup+1;
while(1){
do
inf++;
while(v[inf]!=x && inf<=f);
do
s--;
while(v[s]==x);
if(inf<s)
swap(v+inf,v+s);
else
break;
}
return sup;
}
inline int quickselect(int *v, int l, int r, int k){
if(l>=r)
return v[k];
int p=partition(v,l,r);
int dim=p;
while(v[dim]==v[p] && dim>l)
dim--;
if(k>dim && k<=p)
return v[p];
if(k<=dim)
return quickselect(v,l,dim,k);
return quickselect(v,p+1,r,k);
}
La funzione di partizionamento è uguale a quella implementata nel caso del quicksort generico presentato in questo post.
In questo caso, a differenza della precedente versione, facciamo in modo che tutti gli elementi uguali al pivot si trovino tutti vicini (ultimo ciclo while del codice).
La funzione quickselect sceglie ad ogni passo ricorsivo quale porzione dell’array ordinare, in base al valore del parametro k passato come argomento.
Commenti»
No comments yet — be the first.