By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,820 Members | 1,154 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,820 IT Pros & Developers. It's quick & easy.

nth_element() not compatible in VS2005

P: n/a
when I run the following code in vs2005:
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
nth_element(A, A +1, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
I got output: 1,2,3,4,5,6,7,8,9,10,11,12, obviously, it's all sorted.
but sgi stl said the result should be "5 2 6 1 4 3 7 8 9 10 11 12".
http://www.sgi.com/tech/stl/nth_element.html

does it mean that vs2005 not compatible with stl in this function?

Nov 7 '06 #1
Share this Question
Share on Google+
7 Replies


P: n/a
Hi

zh*********@gmail.com wrote:
when I run the following code in vs2005:
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
nth_element(A, A +1, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
I got output: 1,2,3,4,5,6,7,8,9,10,11,12, obviously, it's all sorted.
but sgi stl said the result should be "5 2 6 1 4 3 7 8 9 10 11 12".
http://www.sgi.com/tech/stl/nth_element.html

does it mean that vs2005 not compatible with stl in this function?
It's not wrong behavior, but it makes me wonder if this is really linear on
average, as required. (Or maybe MS has found an O(n) sorting
algorithm ;-) )

Of course, from one example, you can't tell.

Markus

Nov 7 '06 #2

P: n/a
"Markus Moll" <mo**@rbg.informatik.tu-darmstadt.dewrote in message
news:45***********************@newsspool4.arcor-online.net...
zh*********@gmail.com wrote:
>when I run the following code in vs2005:
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
nth_element(A, A +1, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
I got output: 1,2,3,4,5,6,7,8,9,10,11,12, obviously, it's all sorted.
but sgi stl said the result should be "5 2 6 1 4 3 7 8 9 10 11 12".
http://www.sgi.com/tech/stl/nth_element.html

does it mean that vs2005 not compatible with stl in this function?

It's not wrong behavior, but it makes me wonder if this is really linear
on
average, as required. (Or maybe MS has found an O(n) sorting
algorithm ;-) )
None of the above. Our sort algorithm just does an insertion sort
for small enough sequences, and sometimes it sorts a bit more than
necessary to streamline logic. Its time complexity meets the
requirements of the C++ Standard, and it's generally pretty fast.
Of course, from one example, you can't tell.
Indeed.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Nov 7 '06 #3

P: n/a
I use the following code to test it and It make me sure that VS2005
sort all the element in nth_element.

int A[] = {1,2,3,4,5,6,7,8,9,10,11,12};
const int N = sizeof(A) / sizeof(int);
for(int i=0; i<100; i++)
{
random_shuffle(A, A+N);
nth_element(A, A +rand()%12, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
}

"Markus Moll д
"
Hi

zh*********@gmail.com wrote:
when I run the following code in vs2005:
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
nth_element(A, A +1, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
I got output: 1,2,3,4,5,6,7,8,9,10,11,12, obviously, it's all sorted.
but sgi stl said the result should be "5 2 6 1 4 3 7 8 9 10 11 12".
http://www.sgi.com/tech/stl/nth_element.html

does it mean that vs2005 not compatible with stl in this function?

It's not wrong behavior, but it makes me wonder if this is really linear on
average, as required. (Or maybe MS has found an O(n) sorting
algorithm ;-) )

Of course, from one example, you can't tell.

Markus
Nov 7 '06 #4

P: n/a
Hi

P.J. Plauger wrote:
>It's not wrong behavior, but it makes me wonder if this is really linear
on
average, as required. (Or maybe MS has found an O(n) sorting
algorithm ;-) )

None of the above. Our sort algorithm just does an insertion sort
for small enough sequences, and sometimes it sorts a bit more than
necessary to streamline logic. Its time complexity meets the
requirements of the C++ Standard, and it's generally pretty fast.
Sorry, I haven't thought about that, you're of course right.

Markus

Nov 7 '06 #5

P: n/a
you are right,I just try it. if the size of the sequence is less than
32, it sort all, else it is not sorted.
but I don't know what "sometimes it sorts a bit more than necessary to
streamline logic." mean, would you mind explaining it clearly?

"P.J. Plauger д
None of the above. Our sort algorithm just does an insertion sort
for small enough sequences, and sometimes it sorts a bit more than
necessary to streamline logic. Its time complexity meets the
requirements of the C++ Standard, and it's generally pretty fast.
Of course, from one example, you can't tell.

Indeed.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Nov 7 '06 #6

P: n/a
Markus Moll <mo**@rbg.informatik.tu-darmstadt.dewrote:
(Or maybe MS has found an O(n) sorting
algorithm ;-) )
Well, counting sort/radix sort are O(n), but the constant factors may be
too large for it to be worthwhile in the general case.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Nov 7 '06 #7

P: n/a
<zh*********@gmail.comwrote in message
news:11**********************@k70g2000cwa.googlegr oups.com...
you are right,I just try it. if the size of the sequence is less than
32, it sort all, else it is not sorted.
but I don't know what "sometimes it sorts a bit more than necessary to
streamline logic." mean, would you mind explaining it clearly?

[pjp] Look at the code in the header. It minimizes work by recursively
partitioning the interval, ignoring any elements partitioned past the
Nth element, until it determines that the Nth element must be in order.
But once the partition size gets under 32 elements, it just sorts whatever
is left rather than do upwards of five more partitionings. Grep the header
for _ISORT_MAX to see other places where we stop being clever and
just do a simple sort on the remainder.

"P.J. Plauger д
None of the above. Our sort algorithm just does an insertion sort
for small enough sequences, and sometimes it sorts a bit more than
necessary to streamline logic. Its time complexity meets the
requirements of the C++ Standard, and it's generally pretty fast.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Nov 7 '06 #8

This discussion thread is closed

Replies have been disabled for this discussion.