Quickselect

Quickselect
Esempio di partizionamento
Classe	Algoritmo di selezione
Struttura dati	Array
Caso peggiore temporalmente	$O(n^{2})$
Caso ottimo temporalmente	$O(n)$
Caso medio temporalmente	$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²) 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(n²) 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