Quickselect: differenze tra le versioni

Versione delle 17:11, 14 set 2007

Versione attuale delle 14:55, 19 giu 2023

(18 versioni intermedie di 13 utenti non mostrate)

Riga 1:

{{F|algoritmi|agosto 2014}}

In [[informatica]], '''quickselect''' è un [[algoritmo]] randomizzato ricorsivo che trova il k-esimo elemento di un [[array]] disordinato di grandezza ''n'' eseguendo [[O-grande|O]](n²) confronti nel caso peggiore e [[O-grande|O]](n) nel caso atteso. Si basa sull algoritmo [[Quicksort]].

{{Algoritmo

|name=Quickselect

|classe = Algoritmo di selezione

|immagine = Partition example.svg

|didascalia = Esempio di partizionamento

|struttura dati = [[Array]]

|tempo migliore = <math>O(n)</math>

|tempo medio = <math>O(n)</math>

|tempo = <math>O(n^2)</math>

|spazio =

|ottimale = Sì

}}

In [[informatica]], '''quickselect''' è un [[algoritmo]] randomizzato ricorsivo che trova il k-esimo elemento di un [[array]] disordinato di grandezza ''n'' eseguendo [[O-grande|O]](n²) confronti nel caso peggiore e [[O-grande|O]](n) nel caso atteso. Si basa sull 'algoritmo [[Quicksort]] e sfrutta la metodologia [[prune and search]].

L'algoritmo quicksort ha diverse [[relazione di ricorrenza|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:

<math> T(n) = \mathcal{O}(n) + T\left({n \over 2}\right)</math>

che ha soluzione [[O-grande|O]](n) in base al [[teorema master]].

Se invece si è nel caso peggiore, si ottiene: <math> T(n) = \mathcal{O}(n) + T(n - 1)</math> che ha soluzione [[O-grande|O]](n²) in base al [[teorema master]].

==Implementazione in [[pseudocodice]]==

<sourcesyntaxhighlight lang="text">

<source lang="text">

algoritmo Quickselect(array A, intero K) -> elemento_array

Riga 23 ⟶ 35:

se ( k < |A1| ) allora ritorna Quickselect(A1,k)

altrimenti se ( k > |A1| + |A2| ) allora ritornarestituisci Quickselect(A3, k - |A1| - |A2|)

altrimenti ritornarestituisci x

</syntaxhighlight>

</source>

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]