Sorting algo's
Author
Hey all, what''s some of the quickest sorting algo''s for acendingly sorting an array of ints.
~Main
==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave
The two quickest I know are merge sort and quick sort. I believe quick sort is typically the faster of the two. But quick sort can get slower if the list is already somewhat sorted. And quick sort isn''t always the best tool for the job. I''ve had cases where insertion sort was a better choice. Never have had any reason to use bubble sort, though.
quicksort (what a surprise ! 
)
in C, use qsort()
in C++, use std::sort()
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
)in C, use qsort()
in C++, use std::sort()
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
I''m no expert on sorting, but perhaps some kind of bucket sort would apply to your situation? Depends of course on how much you really care for speed.
Miles
Miles
Depends;
If the ints are all in a fixed range, e.g. between 0 and 100, they can be sorted very efficiently (particularly for a large number of them), I think it''s called bucket sort.
Otherwise, quicksort or merge sort should be fine.
Also, if the ints are already mostly sorted then you''ll want to pick an appropriate algorithm, I can''t quite think what right now but I''m sure someone can tell you.
If the ints are all in a fixed range, e.g. between 0 and 100, they can be sorted very efficiently (particularly for a large number of them), I think it''s called bucket sort.
Otherwise, quicksort or merge sort should be fine.
Also, if the ints are already mostly sorted then you''ll want to pick an appropriate algorithm, I can''t quite think what right now but I''m sure someone can tell you.
quote:Never have had any reason to use bubble sort, though.
Sofisticated implementations of the quick-sort algorithm don''t sort any blocks smaller than a threshold size, and bubble sort is used to finish-up the job at the end.
Author
Actually opened up a book and looked over the syntax for all the algos, quicksort is probally one of the faster for what i'm trying to do.
Rather than making my own algo, i went ahead and used the STD function.
NOTE: Does that create more overhead?
That should work.. i think.
~Main
==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave
[edited by - duhroach on October 4, 2002 1:17:50 PM]
Rather than making my own algo, i went ahead and used the STD function.
NOTE: Does that create more overhead?
struct FrontToBackSort{ bool operator()(object*& rpStart, object*& rpEnd) { return rpStart->z < rpEnd->z; };};void ZSortObjectList(){ std::sort(o_list.begin(),o_list.end(),FrontToBackSort());} That should work.. i think.
~Main
==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave
[edited by - duhroach on October 4, 2002 1:17:50 PM]
merge/heap sort have complexity O(n*logn) worst case; quick sort is O(n*logn) expected case, and O(n*n) worst case.
counting sort (what ya''ll call bucket sort, although I thought that''s something else) and radix sort are O(n).
If you care about speed, rolling your own will always end up being faster. (execution time, not programming time
)
counting sort (what ya''ll call bucket sort, although I thought that''s something else) and radix sort are O(n).
If you care about speed, rolling your own will always end up being faster. (execution time, not programming time
)
If your integers aren''t too big, and they aren''t repeated, you can make an array
int sortedints[MAX_VALUE];
and then use the value of the integers as indices into this array.
Cédric
int sortedints[MAX_VALUE];
and then use the value of the integers as indices into this array.
Cédric
quote:Original post by duhroach
Rather than making my own algo, i went ahead and used the STD function.
NOTE: Does that create more overhead?
No, the comparison function will be inlined in the sort loop. You should be ok. At any rate, you can always benchmark the code.
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
