Algoritmos de Seleção

Um algoritmo de seleção é um algoritmo que encontra o k-ésimo menor número em uma lista de elementos. Alguns casos específicos comuns de aplicação deste algoritmo são encontrar o menor elemento, o maior elemento, e o elemento mediano. A seleção é um sub-problema de outros mais complexos, como encontrar os vizinhos mais próximos, ou encontrar o menor caminho em um grafo.

Nos casos mais simples, achar o mínimo ou máximo, o custo dos algoritmos de seleção é \(O(N)\), porém pode ser melhorado em estruturas de dados ordenadas. Um caso mais complexo, é o caso do valor mediano, para o número de operações continuar sendo \(O(N)\), é preciso utilizar uma área de armazenamento extra, de \(N/2\) elementos.

Se os elementos estão ordenados, em um array, a seleção do k-ésimo elemento é muito simples, no entanto, para ordenar os elementos são necessários \(O(N\lg N)\) operações para algoritmos de ordenação por comparação, que não utilizarão memória adicional (ou utilizarão pouca memória), ou, se for possível utilizar um algoritmo de ordenação por contagem, o número de operações tenderá a \(O(N)\), porém com o consumo de memória bem maior (\(O(N)\)). Devido a falta de acesso randômico, em uma [lista encadeada], somente o acesso ao k-ésimo elemento tem custo \(O(N)\).

Ao invés de ordenar todos os elementos, é possível realizar uma ordenação parcial nos elementos, permitindo separar os k elementos menores, e com cuidado, utilizar apenas uma operação para selecionar o k-ésimo elemento em um array ou em uma lista encadeada.

A implementação de um algoritmo de ordenação de seleção parcial é diretar, necessitando apenas adaptar o algoritmo de ordenação selection sort para executar apenas k iterações, encontrando assim os k menores elementos (Algoritmo 1). Este algoritmo encontrará o k-ésimo elemento com \(O(kN)\) operações. Apesar de ineficiente, o algoritmo pode ser suficientemente eficiente para valores pequenos de k, além de não necessitar de armazenamento extra e de ser um algoritmo bastante simples de implementar.

Seleção do k-ésimo elemento em Python, baseado no selection sort

Quickselect

O quickselect é um algoritmo de seleção relacionado ao algortimo de ordenação quicksort. Assim como o quicksort, o quickselect tem, na média, eficiência muito boa, porém, sofre do mesmo problema de seleção do pivot, podendo, dependendo da ordenação inicial dos dados, ter sua eficiência comprometida.

Utilizando a mesma abordagem do quicksort, o quickselect divide os elementos em "maiores" e "menores" que um pivot. Após essa divisão, se a posição do pivot for a posição k, o elemento desejado foi encontrado e o algoritmo é encerrado, caso contrário, o algoritmo é executado na metade que contém o k-ésimo elemento desejado. Além de encontrar o k-ésimo elemento, o algoritmo executa a ordenação parcial dos elementos.

Uma vez que não é necessário ordenar as duas partes dos dados, apenas a parte onde se encontra o elemento desejado, o algoritmo executará menos operações que na ordenação total. O algoritmo quicksort executa, em média, \(O(N\lg N)\) operações, enquanto o quickselect ecetuta na ordem de \(O(N)\) operações. O consumo de memória também é reduzido, uma vez que as posições intermediárias não precisam ser guardadas, o consumo de memória é baixo e constante, independente do número de elementos (\(O(1)\)).

A implementação do quickselect (Algoritmo 2), utiliza as mesmas primitivas do quicksort, select_pivot() e partition().

Seleção do k-ésimo elemento em Python, baseado no selection sort

quickselect(list, k)
    min = 0
    max = list.length - 1
    while min != max
        pivot = select_pivot(pivot, list, min, max)
        index = partition(list, min, max, pivot)
        if index == k
            return list[index]
        if index > k
            max = index-1
        else
            min = index+1
    return list[min]