c++ - algoritmo para nth_element
algorithm median (2)
Recientemente he descubierto que existe un método llamado nth_element en el STL. Para citar la descripción:
Nth_element es similar a partial_sort, ya que ordena parcialmente un rango de elementos: organiza el rango [primero, último) de manera que el elemento al que apunta el iterador nth sea el mismo que el elemento que estaría en esa posición si todo el rango [primero, último) había sido ordenado. Además, ninguno de los elementos en el rango [nth, último) es menor que cualquiera de los elementos en el rango [first, nth).
Afirma tener una complejidad O (n) en promedio. ¿Cómo funciona el algoritmo? No pude encontrar ninguna explicación para ello.
Lo más probable es que la mediana de las medianas sea algo.
Se llama algoritmo de selección y wikipedia tiene una página decente: http://en.wikipedia.org/wiki/Selection_algorithm
También lea sobre estadísticas de pedidos: http://en.wikipedia.org/wiki/Order_statistic