nth_element() not compatible in VS2005

[zhouchengly]

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?

 

[Markus Moll]

Hi

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

 

[P.J. Plauger]

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

 

[zhouchengly]

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

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

 

[Markus Moll]

Hi

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

 

[zhouchengly]

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 дµÀ£º

 

[Marcus Kwok]

(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.

 

[P.J. Plauger]

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