By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,852 Members | 2,219 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,852 IT Pros & Developers. It's quick & easy.

What is the name of sorting algorithm used in list (STL) class?

P: n/a
Dear All,

What is the name of sorting algorithm used in list (STL) class? and how it
work?
Thanks!!!

Best Regards,
Wahoo
~ Let us linux ~
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 100,000 Newsgroups - 19 Different Servers! =-----
Jul 22 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a

"Wahoo" <wa***@yahoo.com> wrote in message news:40******@lungfunggdn.org...
Dear All,

What is the name of sorting algorithm used in list (STL) class? and how it
work?


It is sort.
E.g.
#include <list>
#include <iostream>
using namespace std;

int main(){
list<int> l;
list<int>::const_iterator itr;
l.push_back(5);
l.push_back(4);
l.push_back(17);
l.push_back(3);
l.sort();
for (itr = l.begin(); itr != l.end(); ++itr)
cout << *itr; //print 34517
}

-Sharad
Jul 22 '05 #2

P: n/a

"Sharad Kala" <no*****************@yahoo.com> schrieb im Newsbeitrag
news:2h************@uni-berlin.de...

"Wahoo" <wa***@yahoo.com> wrote in message

news:40******@lungfunggdn.org...
Dear All,

What is the name of sorting algorithm used in list (STL) class? and how it work?


It is sort.


Er, I think the question was: What does list<T>.sort() do?
I'm not sure if the method is defined in std C++, but only the result
is. To see what your implementation does open the file "list" from
your include directory and search for list().
--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

________________________________________
Looking for a good game? Do it yourself!
GLBasic - you can do
www.GLBasic.com
Jul 22 '05 #3

P: n/a
Wahoo wrote:
Dear All,

What is the name of sorting algorithm used in list (STL) class? and how it
work?
Thanks!!!

Best Regards,
Wahoo
~ Let us linux ~
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 100,000 Newsgroups - 19 Different Servers! =-----


std::lists have a sort method, as demonstrated in another reply by Sharad.

In general you can sort any STL container with a random access iterator
using one of the algorithms listed below, declared in <algorithm>.

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);

template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);

As an example, consider the following:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std ;

int main()
{
vector<unsigned> v ;
unsigned i ;

for (i = 32; i > 0; i--)
v.push_back(i) ;

sort<vector<unsigned>::iterator>(v.begin(), v.end()) ;

copy(v.begin(), v.end(), ostream_iterator<unsigned>(cout, " ")) ;
cout << endl ;

return 0 ;
}

Alan
Jul 22 '05 #4

P: n/a
Alan Johnson wrote:
Wahoo wrote:
Dear All,

What is the name of sorting algorithm used in list (STL) class?


sort<vector<unsigned>::iterator>(v.begin(), v.end()) ;


Actually, and I realized this just after posting, the compiler should be
able to infer the template type from the parameters (is this allowed by
the standard?), so this line could be changed to:

sort(v.begin(), v.end()) ;
Alan
Jul 22 '05 #5

P: n/a
On 19 May 2004 13:27:24 +0800, "Wahoo" <wa***@yahoo.com> wrote:
Dear All,

What is the name of sorting algorithm used in list (STL) class? and how it
work?


I think it's generally implemented as a mergesort, or some variant of
it. It is a divide and conquer algorithm, where to recursively sort
each half of the sequence and then merge the two sorted halves
together - it's a good algorithm for linked lists, since merge is
quite efficient for linked lists.

Tom
--
C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Jul 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.