Sort elements in a std::list?

Discussion in 'C++' started by desktop, Apr 7, 2008.

  1. desktop

    desktop Guest

    How long does it take to sort elements in a std::list in worst case?

    I have read that quicksort on average (depends on partitioning) takes
    O(nlgn). But is quicksort used when sorting a std::list?

    And is it possible to sort faster than O(nlgn) in general - not looking
    a best case?
    desktop, Apr 7, 2008
    #1
    1. Advertising

  2. desktop wrote:
    > How long does it take to sort elements in a std::list in worst case?


    The C++ standard probably doesn't specify, and I haven't actually
    checked what compilers use in practice, but I'm pretty sure most
    compilers use merge sort.

    Merge sort is especially suited for doubly-linked lists because such
    lists can be merge-sorted in-place (ie. only changing prev/next
    pointers), without the need for any additional memory. Merge sort can be
    implemented in such way that it doesn't require random access, and thus
    it can be applied to a list. Given that the worst-case of merge sort is
    O(n*log n), it makes it very efficient regardless of what the list contains.

    > I have read that quicksort on average (depends on partitioning) takes
    > O(nlgn). But is quicksort used when sorting a std::list?


    In theory quicksort could be applied to a list (like merge sort, it's
    possible to implement quicksort in a way that doesn't require random
    access). However, given that the worst-case of quicksort is O(n^2) I
    think most implementations prefer using merge sort, which is very fast
    and in the case of doubly-linked lists doesn't require any additional
    memory (unlike with arrays).

    > And is it possible to sort faster than O(nlgn) in general - not looking
    > a best case?


    It has been mathematically proved that a sorting algorithm which
    is based on comparison between the elements cannot be faster than
    O(n log n). Faster sorting algorithms exist, but they cannot used if
    only comparison between elements is available (they usually only work
    with things like integers). See for example
    http://en.wikipedia.org/wiki/Radix_sort
    Juha Nieminen, Apr 7, 2008
    #2
    1. Advertising

  3. desktop

    Jerry Coffin Guest

    In article <ftdr82$fnl$-c.dk>, says...
    > How long does it take to sort elements in a std::list in worst case?


    The standard doesn't give a worst case for this operation.

    > I have read that quicksort on average (depends on partitioning) takes
    > O(nlgn). But is quicksort used when sorting a std::list?


    The standard doesn't say. It appears to have been written with the idea
    of allowing either Quicksort or merge-sorting as the implementation. In
    theory, it could probably be implemented in other ways (e.g. a heap
    sort) but I'd guess most implementations use one of those two.

    > And is it possible to sort faster than O(nlgn) in general - not looking
    > a best case?


    Not if you sort based on comparisons of the items being sorted. There
    are things like bucket sorts, but the circumstances in which they can be
    applied are fairly restricted.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Apr 7, 2008
    #3
  4. Andy Champ wrote:
    > I have to wonder why you put the elements in a list (rather than, say, a
    > map) if you're going to sort them. Then they could be sorted on-the-fly
    > as they go in...


    A list takes slightly less memory than a set and some operations are
    way faster (such as push_back). Also traversing the list is probably
    faster than traversing a set.

    If you are going to add tons of elements to the data container and
    then sort it, the memory saving of using the list may be worth it.
    Juha Nieminen, Apr 8, 2008
    #4
  5. "Jerry Coffin" <> wrote in message
    news:...
    : In article <ftdr82$fnl$-c.dk>, says...
    : > How long does it take to sort elements in a std::list in worst case?
    :
    : The standard doesn't give a worst case for this operation.
    :
    : > I have read that quicksort on average (depends on partitioning)
    takes
    : > O(nlgn). But is quicksort used when sorting a std::list?
    :
    : The standard doesn't say. It appears to have been written with the
    idea
    : of allowing either Quicksort or merge-sorting as the implementation.
    In
    : theory, it could probably be implemented in other ways (e.g. a heap
    : sort) but I'd guess most implementations use one of those two.

    Note that the standard specifies that std::list::sort results in a
    *stable* sort: that is, the relative order of equivalent elements is not
    changes.
    This basically excludes Quicksort as an implementation.

    The standard also does not mention the existence of a "worst case" for
    std::list::stort, nor the need for allocating memory or copying objects.
    While these omissions are not explicit statements, they would make it
    difficult to use any algorithm other than Mergesort.

    It would be very surprising and difficult for a standard library
    implementation to choose any algorithm different from Mergesort (or some
    derivative of it). All the (major) existing lib implementations use a
    form of Mergesort.

    Regards,
    Ivan
    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
    Brainbench MVP for C++ <> http://www.brainbench.com
    Ivan Vecerina, Apr 8, 2008
    #5
  6. "Ivan Vecerina" <> writes:

    > "Jerry Coffin" <> wrote in message
    > news:...
    > : In article <ftdr82$fnl$-c.dk>, says...
    > : > How long does it take to sort elements in a std::list in worst case?
    > :
    > : The standard doesn't give a worst case for this operation.
    > :
    > : > I have read that quicksort on average (depends on partitioning)
    > takes
    > : > O(nlgn). But is quicksort used when sorting a std::list?
    > :
    > : The standard doesn't say. It appears to have been written with the
    > idea
    > : of allowing either Quicksort or merge-sorting as the implementation.
    > In
    > : theory, it could probably be implemented in other ways (e.g. a heap
    > : sort) but I'd guess most implementations use one of those two.
    >
    > Note that the standard specifies that std::list::sort results in a
    > *stable* sort: that is, the relative order of equivalent elements is not
    > changes.
    > This basically excludes Quicksort as an implementation.


    Not at all. You can easily use a wrapped lessp, that uses the
    'address' of the elements. If the elements are already pointers, then:

    bool wrapped_lessp(T* a,T* b){
    return(lessp(a,b)
    or ((not lessp(b,a))
    and (a<b)));}

    Then no two elements are equal (by wrapped_lessp), but equal elements
    (by lessp) are still sorted together, keeping their original order.

    If the elements are not pointers, then you can spend O(n) to wrap them
    in 'pointers', that is, to sort a vector of indices instead, using:

    bool wrapped_lessp(int a,int b){
    return(lessp(v[a],v)
    or ((not lessp(v,v[a]))
    and (a<b)));}

    Anyways, sorting big lists (more than 3 elements) will be done more
    efficiently by going thru a vector.

    --
    __Pascal Bourguignon__
    Pascal J. Bourguignon, Apr 8, 2008
    #6
  7. desktop

    Jerry Coffin Guest

    In article <2ddc4$47fb8e06$55da1598$>,
    says...

    [ ... ]

    > Note that the standard specifies that std::list::sort results in a
    > *stable* sort: that is, the relative order of equivalent elements is not
    > changes.
    > This basically excludes Quicksort as an implementation.


    Actually, no it doesn't. It's quite trivial for a quick sort on a linked
    list to be stable.

    The usual implementation of quicksort for arrays works by doing two more
    or less separate scans, one from the bottom up and the other from the
    top down. When each finds an element that's out of order compared to the
    chosen pivot, you swap those two elements. This means you need only
    minimal extra storage to partition the array (basically, room for one
    extra element during swapping, plus two positions in the array).

    For linked lists, partitioning is actually simpler: you choose a pivot,
    and then create two linked lists, one of elements that compare less than
    the pivot, and the other of elements greater than or equal to the pivot.
    Since you can move elements around just by manipulating the pointers,
    the only auxiliary storage you need is a position into the linked list,
    and a pointer to the head of the second linked list.

    > The standard also does not mention the existence of a "worst case" for
    > std::list::stort, nor the need for allocating memory or copying objects.
    > While these omissions are not explicit statements, they would make it
    > difficult to use any algorithm other than Mergesort.


    As you may be able to guess from the discussion above, nearly the ONLY
    requirement that would really distinguish between the two would be one
    on worst case performance. Quick sort still have O(N*N) worst case,
    where merge sort is always O(N lg N). Worse, since you don't get random
    access to the elements, you can't really use a median of three or
    anything like that to choose your pivot element; you typically just use
    the first element in the list as the pivot (at least for the first
    partition), making the worst case a bit more common.

    OTOH, once you know the size of a partition, you can swap the element
    from the middle of the list to the beginning. Since std::list is doubly
    linked, you then have access to the first, middle and last elements, so
    you can do a median of three pivot selection on subsequent partitions.
    IOW, while a linked list tends to hurt the performance of quick sort,
    with a little care you can minimize that effect.

    > It would be very surprising and difficult for a standard library
    > implementation to choose any algorithm different from Mergesort (or some
    > derivative of it). All the (major) existing lib implementations use a
    > form of Mergesort.


    It certainly would NOT be difficult to use quick sort. Just to give one
    example, I'm quite sure that P.J. Plaugar would have absolutely NO
    difficulty at all with implementing list::sort as a quick sort.

    The only real question is whether he _would_. For linked lists, quick
    sort provides little or no advantage over a merge sort, but at least in
    theory its worst case is much worse. As such, I suppose seeing it would
    be surprising but (at least to me) only mildly so.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Apr 9, 2008
    #7
  8. desktop

    Jerry Coffin Guest

    In article <>,
    says...

    [ ... ]

    > Not at all. You can easily use a wrapped lessp, that uses the
    > 'address' of the elements. If the elements are already pointers, then:
    >
    > bool wrapped_lessp(T* a,T* b){
    > return(lessp(a,b)
    > or ((not lessp(b,a))
    > and (a<b)));}


    As I pointed out elsethread, this is really completely unnecessary. In
    any case, I don't see how it could work correctly -- the addresses of
    elements in a linked list have no relationship at all to their current
    relative positions in the list.

    > Anyways, sorting big lists (more than 3 elements) will be done more
    > efficiently by going thru a vector.


    The speed difference probably doesn't justify the extra work until you
    get quite a bit larger than 3 elements, but yes, for very many elements
    a vector will generally be faster. Then again, I'll openly admit that
    I'm somewhat biased -- I've pointed out before that I think linked lists
    are heavily overused, and _rarely_ a good choice for much of anything.
    I'd just as soon not get back into that particular discussion at the
    moment though...

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Apr 9, 2008
    #8
  9. desktop

    Kai-Uwe Bux Guest

    Jerry Coffin wrote:

    > In article <>,
    > says...

    [snip]
    >> Anyways, sorting big lists (more than 3 elements) will be done more
    >> efficiently by going thru a vector.

    >
    > The speed difference probably doesn't justify the extra work until you
    > get quite a bit larger than 3 elements, but yes, for very many elements
    > a vector will generally be faster.

    [snip]

    I don't think the size of the sequence will matter all that much, but I
    conjecture that in a speed contest list vs vector on sorting, a list will
    win if swapping the objects is very expensive compared to rearranging some
    pointers. The main reason that quick-sort wins against heap-sort is that
    quick-sort does not move data around so often.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Apr 9, 2008
    #9
  10. desktop

    James Kanze Guest

    On Apr 9, 6:53 am, Jerry Coffin <> wrote:
    > In article <>,
    > says...


    > [ ... ]
    > > Anyways, sorting big lists (more than 3 elements) will be done more
    > > efficiently by going thru a vector.


    > The speed difference probably doesn't justify the extra work
    > until you get quite a bit larger than 3 elements, but yes, for
    > very many elements a vector will generally be faster.


    Doesn't this depend on the type of the elements? Swapping
    elements in a list is just pointer manipulations; swapping them
    in a vector means actually moving the elements themselves. If
    the elements are expensive to copy, and don't support an
    optimized swap, that could make a significant difference.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Apr 9, 2008
    #10
  11. desktop

    Jerry Coffin Guest

    In article <8f828965-ee43-4f83-891e-d950ae26c1e7@
    2g2000hsn.googlegroups.com>, says...

    [ ... sorting list being slower than sorting vector ]

    > Doesn't this depend on the type of the elements? Swapping
    > elements in a list is just pointer manipulations; swapping them
    > in a vector means actually moving the elements themselves. If
    > the elements are expensive to copy, and don't support an
    > optimized swap, that could make a significant difference.


    Yes, that's why I said "generally" -- things stored in a standard
    container should generally be fairly cheap to copy. That's _less_ of an
    issue with std::list than std::vector (for one example) but your object
    is still copied into the collection, so if it's really expensive to
    copy, you probably want to wrap it in something (e.g. a smart pointer)
    to make copying cheap.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Apr 10, 2008
    #11
    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:
    6
    Views:
    640
    Jim Langston
    Oct 30, 2005
  2. Adam Hartshorne
    Replies:
    2
    Views:
    372
    Nitin Motgi
    Jan 27, 2006
  3. Replies:
    4
    Views:
    513
  4. Juha Nieminen
    Replies:
    22
    Views:
    1,019
    Kai-Uwe Bux
    Oct 12, 2007
  5. Navin
    Replies:
    1
    Views:
    684
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page