domingo, 25 de outubro de 2015

Algoritmo de seleção QuickSelect

Olá pessoal, nesse post nós iremos conhecer o algoritmo de seleção QuickSelect. Trata-se de um algoritmo de divisão e conquista que seleciona o k-ésimo menor elemento de um vetor não ordenado.

O Quickselect possui tempo médio de O(n) e no pior caso pode chegar a O(n^2) (mesma complexidade do pior caso do QuickSort).

O QuickSelect se baseia em selecionar e particionar. A função de particionar é exatamente a mesma do QuickSort. Após a partição, faz-se uma busca binária para selecionar. Veja o código:



Nenhum comentário: