nth_element() not compatible in VS2005

Discussion in 'C++' started by zhouchengly@gmail.com, Nov 7, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. Markus Moll Guest

    Hi

    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
    Markus Moll, Nov 7, 2006
    #2
    1. Advertising

  3. P.J. Plauger Guest

    "Markus Moll" <-darmstadt.de> wrote in message
    news:45504a7e$0$18842$-online.net...

    > 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
    P.J. Plauger, Nov 7, 2006
    #3
  4. Guest

    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
    >
    > 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, 2006
    #4
  5. Markus Moll Guest

    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
    Markus Moll, Nov 7, 2006
    #5
  6. Guest

    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, 2006
    #6
  7. Marcus Kwok Guest

    Markus Moll <-darmstadt.de> wrote:
    > (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
    Marcus Kwok, Nov 7, 2006
    #7
  8. P.J. Plauger Guest

    <> wrote in message
    news:...
    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
    P.J. Plauger, Nov 7, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ravikanth[MVP]
    Replies:
    1
    Views:
    350
    Jackal
    Jul 22, 2003
  2. Replies:
    5
    Views:
    917
    Michael DOUBEZ
    Apr 20, 2009
  3. Scott Meyers
    Replies:
    0
    Views:
    664
    Scott Meyers
    Mar 17, 2011
  4. Harold Hausman
    Replies:
    3
    Views:
    186
    Jano Svitok
    Apr 27, 2007
  5. pantagruel
    Replies:
    0
    Views:
    226
    pantagruel
    Feb 17, 2006
Loading...

Share This Page