algorithm for nth_element

Question

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.

IVlad · Accepted Answer · 2010-03-06 13:09:19Z

22

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

answered Mar 6, 2010 at 13:09

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dave Gamble · Accepted Answer · 2010-03-06 13:09:43Z

1

Most likely the median-of-medians algo.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22

answered Mar 6, 2010 at 13:09

Dave Gamble

4,20425 silver badges28 bronze badges

Collectives™ on Stack Overflow

algorithm for nth_element

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related