Quickselect: differenze tra le versioni

Versione delle 17:27, 21 giu 2015

Versione attuale delle 14:55, 19 giu 2023

(6 versioni intermedie di 5 utenti non mostrate)

Riga 1:

{{F|informaticaalgoritmi|agosto 2014}}

{{Algoritmo

|name=Quickselect

|classclasse = Algoritmo di selezione

|imageimmagine =[[File: Partition example.svg|200px]]

|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 36 ⟶ 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}}