Quickselect

Da Wikipedia, l'enciclopedia libera.
Quickselect
Partition example.svg
Esempio di partizionamento
Classe Algoritmo di selezione
Struttura dati Array
Caso peggiore temporalmente
Caso ottimo temporalmente
Caso medio temporalmente
Ottimale

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[modifica | modifica wikitesto]

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