Quickselect: differenze tra le versioni

Versione delle 15:47, 26 ago 2014

Versione attuale delle 14:55, 19 giu 2023

(9 versioni intermedie di 7 utenti non mostrate)

Riga 1:

{{F|informaticaalgoritmi|agosto 2014}}

{{Algoritmo

[[Immagine:Partition example.svg|thumb|upright=0.8|Esempio di partizionamento]]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]].

|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ì

}}

[[Immagine:Partition example.svg|thumb|upright=0.8|Esempio di partizionamento]]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 10 ⟶ 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 24 ⟶ 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}}