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_

def select(data, k):
    for i in range(k):
        index = i
        for j in range(i+1,len(data)):
            if data[j] < data[index]:
                index = j
        data[i],data[index] = data[index],data[i]
    return data[k-1]

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]