Menu
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.
221
The nth_element function is typically implemented using Introselect, which brings the average complexity down to O(n).
If you only want to move the n-th element into place, instead of recursing into both sub-arrays, you can tell in every step whether you will need to descend into the left or right sub-array. (You know this because the n-th element in a sorted array has index n so it becomes a matter of comparing indices.)
nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that: The element pointed at by nth is changed to whatever element would occur in that position if [first, last) were sorted.
Here, we have passed greater () as binary function, so now nth element will be the one which should be at the nth place if we sort the given array in descending order, so first n elements will be the first n largest elements. It can be used to find the median of the elements given.
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
119
Most likely the median-of-medians algo.
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
