Quickselect

Da Wikipedia, l'enciclopedia libera.
Esempio di partizionamento

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:

 T(n) = \mathcal{O}(n) + T\left({n \over 2}\right)

che ha soluzione O(n) in base al teorema master.

Se invece si è nel caso peggiore, si ottiene:  T(n) = \mathcal{O}(n) + T(n - 1) che ha soluzione O(n2) in base al teorema master.

Implementazione in pseudocodice[modifica | modifica sorgente]

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 ritorna Quickselect(A3, k - |A1| - |A2|)
 
      altrimenti ritorna x
informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica