[Sorting] What do you want besides sorting functions
What other sorting related stuff would users like besides just sorting functions? I will try to implement any improvements or new ideas that users want.
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). It's a similar technique to quicksort, except you only aim at finding an element and you care not about the side of the pivot that is not interesting. It is O((log (n)) IIRC. What you think? Regards, Hans On 16-Mar-07, at 2:01 PM, Sam Schetterer wrote:
What other sorting related stuff would users like besides just sorting functions? I will try to implement any improvements or new ideas that users want. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
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? --Michael Fawcett
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 ); }
--Michael Fawcett _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
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
You're right. I was considering nth_element behavior exactly the same as partial_sort. My bad. :) Hans On 16-Mar-07, at 5:11 PM, Michael Fawcett wrote:
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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
participants (3)
-
Hans Larsen -
Michael Fawcett -
Sam Schetterer