# A question regarding stl nth_element

• June 18th, 2013, 02:37 PM
LarryChen
A question regarding stl nth_element
Here is the code,
Code:

```        vector<int> vec;         for(int i=0;i<10;++i)                 vec.push_back(i);         random_shuffle(vec.begin(), vec.end());         nth_element(vec.begin(), vec.begin()+7, vec.end());```
No matter how I choose the second argument passed to nth_element, the elements in vec are always sorted as,
0,1,2,3,4,5,6,7,8,9
What is the use of second argument here?Thanks.
• June 18th, 2013, 02:59 PM
GCDEF
Re: A question regarding stl nth_element
Did you read the documentation? What are you expecting it to do differently?
• June 18th, 2013, 03:08 PM
Paul McKenzie
Re: A question regarding stl nth_element
Quote:

Originally Posted by LarryChen
No matter how I choose the second argument passed to nth_element, the elements in vec are always sorted as,
0,1,2,3,4,5,6,7,8,9
What is the use of second argument here?Thanks.

http://www.cplusplus.com/reference/a...m/nth_element/

Regards,

Paul McKenzie
• June 18th, 2013, 05:23 PM
Philip Nicoletti
Re: A question regarding stl nth_element
Try using a larger number than 10. Looking at the code in Visual C++ 2010, it looks
like if the number of elements is less than or equal to 32, it just does an insertion
sort. So try adding 100 elements.
• June 19th, 2013, 10:39 AM
LarryChen
Re: A question regarding stl nth_element
Quote:

Originally Posted by Philip Nicoletti
Try using a larger number than 10. Looking at the code in Visual C++ 2010, it looks
like if the number of elements is less than or equal to 32, it just does an insertion
sort. So try adding 100 elements.

I tried adding 100 elements this time, here is the code and results.
Code:

```        vector<int> vec;         for(int i=0;i<100;++i)                 vec.push_back(i);         random_shuffle(vec.begin(), vec.end());         nth_element(vec.begin(), vec.begin()+3, vec.end());```
I tried n=3 and n=7. but the results are exactly the same,
vec[100](0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,24,28,21,42,29,41,40,30,32,33,31,23,37,27,35,38,39,25,26,36,20,34,19,22,43,98,96,58,82,86,90,62,59,97,55,78,68,50,61,46,44,83,56,87,60,84,95,57,54,81,77,70,89,99,79,73,76,65,66,88,64,47,52,72,53,67,94,85,75,74,69,45,91,93,51,48,80,71,63,49,92)
It looks like before 18, the numbers are sorted. What does it mean? Thanks.
• June 19th, 2013, 10:58 AM
GCDEF
Re: A question regarding stl nth_element
There's nothing wrong with those results. It's doing what it's documented to do. What's the issue?
• June 19th, 2013, 12:02 PM
LarryChen
Re: A question regarding stl nth_element
Quote:

Originally Posted by GCDEF
There's nothing wrong with those results. It's doing what it's documented to do. What's the issue?

The issue is that since no matter what is passed to the second parameter of nth_element, the result is always the same, why would we need the second parameter?Thanks.
• June 19th, 2013, 12:13 PM
GCDEF
Re: A question regarding stl nth_element
It takes all values in the container and rearranges the container so that all values less than the nth element will occur before it in the result, and all values greater will occur after. That's all it says about the sort order. So, if your vector contains

1,3,9,8,2,6,0,4,5 and you use 7 for your second argument, which in this case is the value 4, all values less than 4 will be placed first in the vector, followed by 4, followed by all values greater than 4. Other than that, the sort order isn't specified. So it may look like

1,3,2,0,4,5,6,9,8 or 0,3,2,1,4,8,6,9,5 or any other combination such that all values before the nth element are <= the nth element and all values after it are >=.
• June 19th, 2013, 01:16 PM
Philip Nicoletti
Re: A question regarding stl nth_element
Quote:

The issue is that since no matter what is passed to the second parameter of nth_element, the result is always the same, why would we need the second parameter?Thanks.
How many values of n did you try ? What happens if you use 40 ?