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

W

Wahoo

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 ~
 
S

Sharad Kala

Wahoo said:
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
 
G

Gernot Frisch

Sharad Kala said:
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
 
A

Alan Johnson

Wahoo said:
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 ~

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
 
A

Alan Johnson

Alan said:
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
 
T

tom_usenet

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top