Seleção rápida - Quickselect

Seleção rápida

Visualização animada do algoritmo de seleção rápida. Selecionando o 22º menor valor.
Aula	Algoritmo de seleção
Estrutura de dados	Variedade
Desempenho de pior caso	О ( n 2 )
Melhor caso de desempenho	О ( n )
Desempenho médio	O ( n )

Em ciência da computação , QuickSelect é um algoritmo de seleção para encontrar o k th menor elemento em uma lista não ordenada. Está relacionado ao algoritmo de classificação quicksort . Como o quicksort, ele foi desenvolvido por Tony Hoare e, portanto, também é conhecido como algoritmo de seleção de Hoare . Como o quicksort, é eficiente na prática e tem bom desempenho de caso médio, mas tem desempenho de pior caso ruim. Quickselect e suas variantes são os algoritmos de seleção usados ​​com mais frequência em implementações eficientes do mundo real.

O Quickselect usa a mesma abordagem geral do quicksort, escolhendo um elemento como pivô e particionando os dados em dois com base no pivô, de acordo como menor ou maior que o pivô. No entanto, em vez de recorrer a ambos os lados, como no quicksort, a seleção rápida recorre apenas a um lado - o lado com o elemento que está procurando. Isso reduz a complexidade média de a , com o pior caso de . ${\ displaystyle O (n \ log n)}$${\ displaystyle O (n)}$${\ displaystyle O (n ^ {2})}$

Tal como acontece com o quicksort, o quickselect é geralmente implementado como um algoritmo no local e, além de selecionar o k- ésimo elemento, ele também classifica parcialmente os dados. Consulte o algoritmo de seleção para uma discussão mais aprofundada da conexão com a classificação.

Algoritmo

No quicksort, existe um subprocedimento denominado partitionque pode, em tempo linear, agrupar uma lista (variando de índices lefta right) em duas partes: aquelas menores que um determinado elemento e aquelas maiores ou iguais ao elemento. Aqui está o pseudocódigo que executa uma partição sobre o 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

Isso é conhecido como esquema de partição Lomuto , que é mais simples, mas menos eficiente do que o esquema de partição original de Hoare .

No quicksort, classificamos recursivamente os dois ramos, levando ao tempo do melhor caso . No entanto, ao fazer a seleção, já sabemos em qual partição está nosso elemento desejado, uma vez que o pivô está em sua posição final classificada, com todos os que o precedem em uma ordem não classificada e todos os que o seguem em uma ordem não classificada. Portanto, uma única chamada recursiva localiza o elemento desejado na partição correta e nos baseamos nisso para a seleção rápida: ${\ displaystyle 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) 

Observe a semelhança com o quicksort: assim como o algoritmo de seleção baseado em mínimo é um tipo de seleção parcial, este é um quicksort parcial, gerando e particionando apenas suas partições. Este procedimento simples tem desempenho linear esperado e, como o quicksort, tem um desempenho muito bom na prática. É também um algoritmo local , exigindo apenas sobrecarga de memória constante se a otimização da chamada final estiver disponível ou se eliminar a recursão final com um loop: ${\ displaystyle O (\ log n)}$${\ displaystyle 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

Complexidade de tempo

Como o quicksort, o quickselect tem um bom desempenho médio, mas é sensível ao pivô escolhido. Se bons pivôs são escolhidos, ou seja, aqueles que diminuem consistentemente o conjunto de pesquisa em uma determinada fração, o conjunto de pesquisa diminui de tamanho exponencialmente e por indução (ou soma da série geométrica ) vê-se que o desempenho é linear, pois cada etapa é linear e o tempo total é uma constante vezes isso (dependendo da rapidez com que o conjunto de pesquisa se reduz). No entanto, se pivôs maus são consistentemente escolhido, tais como diminuindo em apenas um único elemento de cada vez, em seguida, desempenho pior caso é quadrática: . Isso ocorre, por exemplo, ao procurar o elemento máximo de um conjunto, usando o primeiro elemento como o pivô e tendo os dados classificados. ${\ displaystyle O (n ^ {2})}$

Variantes

A solução mais fácil é escolher um pivô aleatório, que produz um tempo linear quase certo . Deterministicamente, pode-se usar a estratégia de pivô mediana de 3 (como no quicksort), que produz desempenho linear em dados parcialmente classificados, como é comum no mundo real. No entanto, as sequências planejadas ainda podem causar a complexidade do pior caso; David Musser descreve uma sequência de "mediana de 3 killer" que permite um ataque contra essa estratégia, o que foi uma motivação para seu algoritmo de introseleção .

Pode-se garantir desempenho linear mesmo no pior caso, usando uma estratégia de pivô mais sofisticada; isso é feito no algoritmo da mediana das medianas . No entanto, a sobrecarga de calcular o pivô é alta e, portanto, geralmente não é usado na prática. Pode-se combinar a seleção rápida básica com a mediana das medianas como fallback para obter o desempenho médio rápido do caso e o desempenho linear do pior caso; isso é feito no introselect .

Cálculos mais finos da complexidade de tempo médio geram um pior caso de pivôs aleatórios (no caso da mediana; outros k são mais rápidos). A constante pode ser melhorada para 3/2 por uma estratégia de pivô mais complicada, gerando o algoritmo Floyd-Rivest , que tem complexidade média de para mediana, com outro k sendo mais rápido. ${\ displaystyle n (2 + 2 \ log 2 + o (1)) \ leq 3.4n + o (n)}$${\ displaystyle 1.5n + O (n ^ {1/2})}$

Veja também

• Algoritmo Floyd-Rivest
• Introselect
• Mediana de medianas

Referências

links externos

• " qselect ", algoritmo Quickselect em Matlab, Manolis Lourakis