jump to navigation

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: , , , , ,
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 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 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=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); } [/sourcecode] 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.

Annunci

Commenti»

No comments yet — be the first.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: