Selezione rapida - Quickselect

Selezione rapida
	Visualizzazione animata dell'algoritmo di selezione rapida. Selezione del 22° valore più piccolo.
Classe	Algoritmo di selezione
Struttura dati	Vettore
Prestazioni nel caso peggiore	( n 2 )
Best-caso le prestazioni	( n )
Prestazioni medie	O( n )

In informatica , quickselect è un algoritmo di selezione per trovare il k- esimo elemento più piccolo in una lista non ordinata. È correlato all'algoritmo di ordinamento Quicksort . Come Quicksort, è stato sviluppato da Tony Hoare , ed è quindi noto anche come algoritmo di selezione di Hoare . Come Quicksort, è efficiente nella pratica e ha buone prestazioni nel caso medio, ma ha prestazioni scadenti nel caso peggiore. Quickselect e le sue varianti sono gli algoritmi di selezione più utilizzati nelle implementazioni efficienti del mondo reale.

Quickselect utilizza lo stesso approccio generale di Quicksort, scegliendo un elemento come pivot e partizionando i dati in due in base al pivot, di conseguenza come minore o maggiore del pivot. Tuttavia, invece di ricorrere su entrambi i lati, come in quicksort, quickselect ricorre solo su un lato: il lato con l'elemento che sta cercando. Ciò riduce la complessità media da a , con un caso peggiore di . $O(n\log n)$ $O(n)$ $O(n^{2})$

Come con quicksort, quickselect è generalmente implementato come un algoritmo sul posto e, oltre a selezionare il $k-$ esimo elemento, ordina anche parzialmente i dati. Vedere l' algoritmo di selezione per ulteriori discussioni sulla connessione con l'ordinamento.

Algoritmo

In Quicksort esiste una sottoprocedura chiamata partitionche può, in tempo lineare, raggruppare una lista (che va da indici lefta right) in due parti: quelle minori di un certo elemento, e quelle maggiori o uguali all'elemento. Ecco lo pseudocodice che esegue una partizione sull'elemento list[pivotIndex]:

function partition(list, left, right, pivotIndex) is
    pivotValue := list[pivotIndex]
    swap list[pivotIndex] and list[right]  // Move pivot to end
    storeIndex := left
    for i from left to right − 1 do
        if list[i] < pivotValue then
            swap list[storeIndex] and list[i]
            increment storeIndex
    swap list[right] and list[storeIndex]  // Move pivot to its final place
    return storeIndex

Questo è noto come schema di partizione di Lomuto , che è più semplice ma meno efficiente dello schema di partizione originale di Hoare .

In Quicksort, ordiniamo ricorsivamente entrambi i rami, portando al tempo migliore . Tuttavia, quando si effettua la selezione, sappiamo già in quale partizione si trova l'elemento desiderato, poiché il pivot è nella sua posizione finale ordinata, con tutti quelli che lo precedono in un ordine non ordinato e tutti quelli che lo seguono in un ordine non ordinato. Pertanto, una singola chiamata ricorsiva individua l'elemento desiderato nella partizione corretta e ci basiamo su questo per la selezione rapida: $O(n\log n)$

// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
function select(list, left, right, k) is
    if left = right then   // If the list contains only one element,
        return list[left]  // return that element
    pivotIndex  := ...     // select a pivotIndex between left and right,
                           // e.g., left + floor(rand() % (right − left + 1))
    pivotIndex  := partition(list, left, right, pivotIndex)
    // The pivot is in its final sorted position
    if k = pivotIndex then
        return list[k]
    else if k < pivotIndex then
        return select(list, left, pivotIndex − 1, k)
    else
        return select(list, pivotIndex + 1, right, k)

Notare la somiglianza con il quicksort: proprio come l'algoritmo di selezione basato sul minimo è un ordinamento di selezione parziale, questo è un quicksort parziale, che genera e partiziona solo le sue partizioni. Questa semplice procedura ha previsto prestazioni lineari e, come Quicksort, ha prestazioni abbastanza buone nella pratica. È anche un algoritmo sul posto , che richiede solo un sovraccarico di memoria costante se è disponibile l'ottimizzazione della chiamata in coda o se si elimina la ricorsione in coda con un ciclo: $O(\log n)$ $O(n)$

function select(list, left, right, k) is
    loop
        if left = right then
            return list[left]
        pivotIndex := ...     // select pivotIndex between left and right
        pivotIndex := partition(list, left, right, pivotIndex)
        if k = pivotIndex then
            return list[k]
        else if k < pivotIndex then
            right := pivotIndex − 1
        else
            left := pivotIndex + 1

Complessità temporale

Come quicksort, quickselect ha buone prestazioni medie, ma è sensibile al pivot scelto. Se si scelgono buoni pivot, cioè quelli che riducono consistentemente l'insieme di ricerca di una data frazione, allora l'insieme di ricerca diminuisce di dimensione in modo esponenziale e per induzione (o sommando la serie geometrica ) si vede che le prestazioni sono lineari, poiché ogni passo è lineare e il tempo complessivo è una costante moltiplicata per questo (a seconda di quanto velocemente si riduce il set di ricerca). Tuttavia, se vengono scelti in modo coerente pivot difettosi, ad esempio diminuendo di un solo elemento ogni volta, la prestazione nel caso peggiore è quadratica: . Ciò si verifica ad esempio nella ricerca dell'elemento massimo di un insieme, utilizzando il primo elemento come pivot e avendo i dati ordinati. $O(n^{2})$

varianti

La soluzione più semplice è scegliere un pivot casuale, che produce un tempo lineare quasi certo . Deterministicamente, si può usare la strategia pivot mediana di 3 (come nel Quicksort), che produce prestazioni lineari su dati parzialmente ordinati, come è comune nel mondo reale. Tuttavia, le sequenze artificiose possono ancora causare la complessità del caso peggiore; David Musser descrive una sequenza "killer mediana di 3" che consente un attacco contro quella strategia, che è stata una delle motivazioni per il suo algoritmo di introselect .

Si possono assicurare prestazioni lineari anche nel peggiore dei casi utilizzando una strategia pivot più sofisticata; questo viene fatto nella mediana dell'algoritmo delle mediane . Tuttavia, l'overhead del calcolo del pivot è elevato e quindi generalmente non viene utilizzato nella pratica. È possibile combinare la selezione rapida di base con la mediana delle mediane come fallback per ottenere sia prestazioni veloci nel caso medio che prestazioni lineari nel caso peggiore; questo viene fatto in introselect .

Calcoli più fini della complessità temporale media producono un caso peggiore di per i pivot casuali (nel caso della mediana; altri k sono più veloci). La costante può essere migliorata a 3/2 con una strategia pivot più complicata, ottenendo l' algoritmo di Floyd-Rivest , che ha una complessità media di per mediana, con altri k più veloci. $n(2+2\log 2+o(1))\leq 3.4n+o(n)$ $1.5n+O(n^{1/2})$

Guarda anche

Riferimenti

link esterno

" qselect ", algoritmo Quickselect in Matlab, Manolis Lourakis

Languages

In other projects