Algoritmo para nth_element [fechado

Question

Recentemente descobri que existe um método chamado nth_element No STL. Para citar a descrição:

Nth_element é semelhante ao parcial_sort, na medida em que ordena parcialmente uma série de elementos: organiza o intervalo [primeiro, último), de modo que o elemento apontado pelo iteador Nth é o mesmo que o elemento que estaria nessa posição se todo o Range [primeiro, último) foi classificado. Além disso, nenhum dos elementos do intervalo [Nth, por último) é menor que qualquer um dos elementos do intervalo [primeiro, Nth).

Ele afirma ter a complexidade O (n) em média. Como funciona o algoritmo? Não consegui encontrar nenhuma explicação para isso.

Answer 1

É chamado de algoritmo de seleção e a Wikipedia tem uma página decente: http://en.wikipedia.org/wiki/selection_algorithm

Leia também sobre estatísticas de pedidos: http://en.wikipedia.org/wiki/order_statistic

Answer 2

Provavelmente, o algo mediano de medicina.

http://en.wikipedia.org/wiki/selection_algorithm#linear_general_selection_algorithm_-_.22median_of_medians_algorithm.22