On 3/16/07, Hans Larsen <hans@poltras.com> wrote:
On 16-Mar-07, at 4:42 PM, Michael Fawcett wrote:
On 3/16/07, Hans Larsen <hans@poltras.com> wrote:
Maybe finding the nth element of an array, without actually sorting the array. This could be useful for finding 2nd min/max and median of an array reusing the same algorithm.
This is actually quite easy, and may have already been implemented in boost or stl (but i haven't found it yet).
std::nth_element perhaps?
Not exactly. nth_element merely takes the pivot that you give and put it into place.
What I'm looking at is a function that, given a position, returns the element that correspond to that position when array is sorted.
Hans
Exemple: template< class V > V::value_type& get_median( V& vec ) { return boost::sorting::__func__( vec.begin(), vec.end(), vec.size () / 2 ); }
Sorry, I guess I'm having trouble understanding how that is different. From MSDN article on nth_element: "Partitions a range of elements, correctly locating the nth element of the sequence in the range so that all the elements in front of it are less than or equal to it and all the elements that follow it in the sequence are greater than or equal to it." In your example, nth_element would return the median value. In other words, the value that would be located at vec.size() / 2 if vec were completely sorted. --Michael Fawcett