In informatica, quickselect è un algoritmo randomizzato ricorsivo che trova il k-esimo elemento di un array disordinato di grandezza n eseguendo O(n2) confronti nel caso peggiore e O(n) nel caso atteso. Si basa sull'algoritmo Quicksort e sfrutta la metodologia prune and search.
L'algoritmo quicksort ha diverse relazioni di ricorrenza, dovute al tipo di problema di minore entità che si viene a creare ogni volta che l'algoritmo viene eseguito. Se ogni chiamata ricorsiva dimezza il problema, si ha:
che ha soluzione O(n) in base al teorema master.
Se invece si è nel caso peggiore, si ottiene: che ha soluzione O(n2) in base al teorema master.
Implementazione in pseudocodice algoritmo Quickselect(array A, intero K) -> elemento_array
seleziona un elemento_array x in A partiziona A rispetto ad x calcolando:
A1 = { y appartenente ad A : y < x } A2 = { y appartenente ad A : y = x } A3 = { y appartenente ad A : y > x }
se ( k < |A1| ) allora ritorna Quickselect(A1,k)
altrimenti se ( k > |A1| + |A2| ) allora restituisci Quickselect(A3, k - |A1| - |A2|)
altrimenti restituisci x
Categoria:Algoritmi