Quickselect: differenze tra le versioni

Versione delle 14:27, 8 feb 2017

Versione attuale delle 14:55, 19 giu 2023

(3 versioni intermedie di 3 utenti non mostrate)

Riga 2:

{{Algoritmo

|name=Quickselect

|classclasse = Algoritmo di selezione

|imageimmagine = Partition example.svg

|captiondidascalia = Esempio di partizionamento

|datastruttura dati = [[Array]]

|best-timetempo migliore = <math>O(n)</math>

|average-timetempo medio = <math>O(n)</math>

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

|spazio =

|space=

|optimalottimale = 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:

Riga 22:

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 40 ⟶ 39:

altrimenti restituisci x

</syntaxhighlight>

</source>

{{portale|informatica}}