Prev: Why does a base function hide a function in a derived class?
Next: Output Generated From Templates
From: Awashesh Kumar on 11 Aug 2010 22:04
I was wondering how is list member function sort implemented in STL.
Since list has bidirectional iterator so any of the random access
iterator based sorting algorithms (heap sort, quick sort etc) can not
be applied on lists. Still the complexity of list::sort is NlogN. So
which algorithm does it apply? I tried to look at algorithm.h where
some sort algos use introsort ( a mix of quick and heap sort) , but
still could not get how it is done for list. There is one way which I
can think of the way STL might implement list::sort is that is copies
list elements into a vector , applies any NlogN algo to sort the
elements and copies back the list. Any other thoughts on efficiency
of sorting on list??

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ulrich Eckhardt on 12 Aug 2010 04:49
Awashesh Kumar wrote:
> Since list has bidirectional iterator so any of the random access
> iterator based sorting algorithms (heap sort, quick sort etc) can not
> be applied on lists.

I wouldn't say that quick sort (not sure about heap sort) requires random
access. Actually, a typical implementation using a linked list is much more
suitable for sorting because reordering just involves fiddling pointers,
not use of things like swap() or even deep copying.

Uli

--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Mathias Gaunard on 12 Aug 2010 05:45
On Aug 12, 2:04 pm, Awashesh Kumar <awashesh.ku...(a)gmail.com> wrote:
> I was wondering how is list member function sort implemented in STL.
> Since list has bidirectional iterator so any of the random access
> iterator based sorting algorithms (heap sort, quick sort etc) can not
> be applied on lists. Still the complexity of list::sort is NlogN. So
> which algorithm does it apply?

In-place merge sort.

It's O(nlogn) run time, O(1) memory usage.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Kaba on 12 Aug 2010 08:29
Awashesh Kumar wrote:
> I was wondering how is list member function sort implemented in STL.

Probably by merge sort. See for example:

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

--
http://kaba.hilvi.org

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Jeremy on 12 Aug 2010 08:22
On Aug 12, 2:49 pm, Ulrich Eckhardt <eckha...(a)satorlaser.com> wrote:
> Awashesh Kumar wrote:
> > Since list has bidirectional iterator so any of the random access
> > iterator based sorting algorithms (heap sort, quick sort etc) can not
> > be applied on lists.
>

Would a sort member function need to use iterators at all? Why
couldn't the std::list just use a nlogn, in-place sorting algorithm
like quick or heap.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: Why does a base function hide a function in a derived class?
Next: Output Generated From Templates