algorithm for nth_element

c++ algorithm median nth-element
martinus picture martinus · Mar 6, 2010 · Viewed 12k times · Source

I have recently found out that there exists a method called nth_element in the STL. To quote the description:

Nth_element is similar to partial_sort, in that it partially orders a range of elements: it arranges the range [first, last) such that the element pointed to by the iterator nth is the same as the element that would be in that position if the entire range [first, last) had been sorted. Additionally, none of the elements in the range [nth, last) is less than any of the elements in the range [first, nth).

It claims to have O(n) complexity on average. How does the algorithm work? I could not find any explanation for it.

Answer

IVlad picture IVlad · Mar 6, 2010

It's called a selection algorithm and wikipedia has a decent page on it: http://en.wikipedia.org/wiki/Selection_algorithm

Also read about order statistics: http://en.wikipedia.org/wiki/Order_statistic

Related questions

C++ Efficiently Calculating a Running Median

Those of you that have read my previous questions know about my work at understanding and implementing quicksort and quickselect, as well as some other basic algorithms. Quickselect is used to calculate the kth smallest element in an unsorted list, …

Read More
What is the right approach when using STL container for median calculation?

Let's say I need to retrieve the median from a sequence of 1000000 random numeric values. If using anything but std::list, I have no (built-in) way to sort sequence for median calculation. If using std::list, I can't randomly access …

Read More
Number of comparisons made in median of 3 function?

As of right now, my functioin finds the median of 3 numbers and sorts them, but it always makes three comparisons. I'm thinking I can use a nested if statement somewhere so that sometimes my function will only make two comparisons. …

Read More