Quickselect

Quickselect
Esempio di partizionamento
Classe	Algoritmo di selezione
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(n^{2})}$
Caso ottimo temporalmente	${\displaystyle O(n)}$
Caso medio temporalmente	${\displaystyle O(n)}$
Ottimale	Sì

In informatica, quickselect è un algoritmo randomizzato ricorsivo che trova il k-esimo elemento di un array disordinato di grandezza n eseguendo O(n^2) 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:

${\displaystyle 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: ${\displaystyle T(n)={\mathcal {O}}(n)+T(n-1)}$ che ha soluzione O(n^2) 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