nth_element + sort versus partial_sort

Discussion in 'C++' started by Scott Meyers, Mar 17, 2011.

  1. Scott Meyers

    Scott Meyers Guest

    At http://wordaligned.org/articles/top-ten-percent , Thomas Guest shows
    how he found that running nth_element followed by sort produced results
    *much* faster than simply running partial_sort. I ran the test myself,
    and I got the same kinds of results he did. I've mentioned this to
    others, and some have been motivated to run the test themselves.
    They've been as astonished as me at the results.

    On the other hand, I ran across this at http://tinyurl.com/47qhrqy :

    > I recently stumbled across partial_sort in stl; fwiw,
    > std:partial_sort( A, A + sqrt(N), A + N ) is ~ 10 times faster than
    > std:sort
    > on my old mac ppc, even for N 100.
    > Also fwiw, nth_element alone is ~ twice as slow as partial_sort --
    > odd.


    What are others' experiences with and comments about using nth_element
    followed by sort instead of partial_sort to sort the top part of some
    range of values? For purposes of discussion, assume that random access
    iterators are available.

    Thanks,

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Aug 7-10 in Banff
    (http://cppandbeyond.com/)
    Scott Meyers, Mar 17, 2011
    #1
    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. Replies:
    7
    Views:
    528
    P.J. Plauger
    Nov 7, 2006
  2. puzzlecracker
    Replies:
    4
    Views:
    654
    Zeppe
    Oct 13, 2008
  3. Replies:
    5
    Views:
    925
    Michael DOUBEZ
    Apr 20, 2009
  4. Navin
    Replies:
    1
    Views:
    684
    Ken Schaefer
    Sep 9, 2003
  5. Paul Butcher
    Replies:
    12
    Views:
    702
    Gary Wright
    Nov 28, 2007
Loading...

Share This Page