From Sedgewick''s Algorithms
Quicksort:
- Unstable
- Worst: O(N²/2)
- Average: O(2N ln(N) )
Mergesort:
- Stable
- Always: O(N lg(N) )
- Use extra space proportional to N
He also mentions that quicksort can perform poorly on data that is practically sorted.
Obvious advice: try both and see which one is best for you. That''s what generic algorithms are for.
Cédric
stl list < pointer > and sorting = bad?
your profiler can''t handle .h files? weird, very weird..
simple solution: open the .h file, copy the code out of it into your cpp testfile, don''t include the .h file and profile:D
this is weird, very weird.. athons perform bether on the slower algo:D
"take a look around" - limp bizkit
www.google.com
simple solution: open the .h file, copy the code out of it into your cpp testfile, don''t include the .h file and profile:D
this is weird, very weird.. athons perform bether on the slower algo:D
"take a look around" - limp bizkit
www.google.com
quote:Original post by cedricl
From Sedgewick''s Algorithms
Quicksort:
- Unstable
- Worst: O(N²/2)
- Average: O(2N ln(N) )
Mergesort:
- Stable
- Always: O(N lg(N) )
- Use extra space proportional to N
In general, maybe, but lists can be merge sorted with constant extra space.
Merge sort''s constant factors are typically better than other n log n sorts; it''s the space requirements that tend to hurt it.
Could someone with an access to both processors confirm my results? Or prove me wrong? I''m really curios on this. I used tried both VC6 and 7''s stl versions.
His question was on how to sort a list of pointers ( and not by memory address ) which i answered. However, on the std::sort vs std::stable_sort issue: Yes, stable_sort can fun faster than sort depending on the order of the data before the sort is executed, and available memory. And my materials state that if the worst case senario for sort is a priority, then using stable_sort is a good fall back.
[edited by - godballz on October 3, 2002 2:20:09 PM]
[edited by - godballz on October 3, 2002 2:20:09 PM]
Author
sorry, the code from godballz doesnt work for me =(
i use msvc6sp5.
the compiler complains about:
error C2661: ''sort'' : no overloaded function takes 3 parameters
thanks any way to every one that tries to help me... and i cant just use an array because the data is quite dynamic =/
//ziruz
------------------------------------------------------------
XL is comming soon @ http://ziruz.cjb.net/
i use msvc6sp5.
the compiler complains about:
error C2661: ''sort'' : no overloaded function takes 3 parameters
thanks any way to every one that tries to help me... and i cant just use an array because the data is quite dynamic =/
//ziruz
------------------------------------------------------------
XL is comming soon @ http://ziruz.cjb.net/
Wow, there are some errors with that code, but I think you''re out of luck with MSVC6.0. Looks like MSVC STL does something pretty un-swift once again. In list.:
typedef greater<_Ty> _Pr3;
void sort(_Pr3 _Pr)
So basically you can''t make it work. If you have the next rev (VS.NET), the following code works:
HTTP 500 retry #1..
typedef greater<_Ty> _Pr3;
void sort(_Pr3 _Pr)
So basically you can''t make it work. If you have the next rev (VS.NET), the following code works:
#include <list>#include <iostream>#include <algorithm>template<typename T>class DeletePtr {public: void operator()(T*elem) { delete elem; }};template<typename T>class IsGreater {public: bool operator()(T l, T r) const { return (*l) > (*r); }};void main(){ std::list<int*> mylist; mylist.push_back(new int(5)); mylist.push_back(new int(2)); mylist.push_back(new int(8)); mylist.sort(IsGreater<int*> ()); std::list<int*>::const_iterator i, endi = mylist.end(); for(i = mylist.begin(); i != endi; ++i) { std::cout<<**i<<std::endl; } std::for_each(mylist.begin(), mylist.end(), DeletePtr<int>());} HTTP 500 retry #1..
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement