Original Post
🔒 Locked
Sorting algo's
Advertisement
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.
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
)
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 ]
radix rocks.. never done it myself but it is O(n) hehe.
"take a look around" - limp bizkit
www.google.com
"take a look around" - limp bizkit
www.google.com
How you sort is important, but you should also give just as much if not more thought to where and when you sort. Always remember that the fastest sort is no sort at all.
quote:Insertion sort. The selection sort looks like this:
Original post by Anonymous Poster
I''ve actually seen selection sort for this purpose because it excels at sorting sequences of elements that are not too far from their final position. Are you sure you meant bubble sort?
for (T i = begin; i != end; ++i)
std::swap(i, std::min_element(i, end)); // from memory
Anyway, it''s worth looking into the radix sort - the O(n) complexity has its advantages
quote:
Original post by davepermen
radix rocks.. never done it myself but it is O(n) hehe.
True, radix sort is O(n) but the constant is high so for most practical n a O(n lg n) average algorithm (like quicksort) will actually be faster in practice since they usually have a low contant.
Asymtotic comparisons are great but you can''t forget practical benchmarks.
- mongrelprogrammer
quote:
Original post by cedricl
If your integers aren''t too big, and they aren''t repeated, you can make an array
int sortedints[MAX_VALUE];
quote:
Original post by Neosmyle
That is the basis of the radix sort, but the radix sort allows you to have larger numbers, and they can be repeated.
Umm... you wouldn''t be saying that you can''t have repeat values in bucket sort are you? Because that would just be crazy...
- mongrelprogrammer
quote:
Original post by mongrelprogrammer
Umm... you wouldn''t be saying that you can''t have repeat values in bucket sort are you? Because that would just be crazy...
I never said that. I just said that inserting values into an array is where the radix sort comes from. However, just putting elements into the array does not allow for repeating entries, and it leaves empty space.
The concept behind the radix sort is to use an "offset table," which helps to insert elements into the array with no empty space, and with support for repeating entries.
quote:
Original post by cedricl
If your integers aren''t too big, and they aren''t repeated, you can make an array
int sortedints[MAX_VALUE];
quote:
Original post by Neosmyle
I never said that. I just said that inserting values into an array is where the radix sort comes from. However, just putting elements into the array does not allow for repeating entries, and it leaves empty space.
Actually it was cedric that I was really addressing, you just seemed to agree with him so you got lumped in the bunch since you said:
quote:
Original post by Neosmyle
That is the basis of the radix sort, but the radix sort allows you to have larger numbers, and they can be repeated.
But since cedric was actually talking about using the values to be sorted as array indecies and not be ''incerted'' into the array he mistakenly said that they could not be repeated (which is, of course, incorrect).
- mongrelprogrammer
quote:
Original post by mongrelprogrammer
But since cedric was actually talking about using the values to be sorted as array indecies and not be ''incerted'' into the array he mistakenly said that they could not be repeated (which is, of course, incorrect).
I''m not sure what you are trying to say here, but cedric''s original post was completely correct:
quote:
Original post by cedric
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.
I was merely trying to say that the radix sort stems from this idea, but it creates an offset table, so that entries can be repeated, and so there is no empty space between entries.
quote:
Original post by Neosmyle
I''m not sure what you are trying to say here, but cedric''s original post was completely correct:
quote:
Original post by cedric
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.
Umm... No, it wasn''t. He said to create an array and use the integers and indeces into the array, aka bucketsort. However, he also said that it would work as long as they "aren''t repeated". This is wrong. He is wrong for saying it. You are wrong for saying he is right for saying it.
This method clearly works for repeated data since the value of the data is intrinsic to the indice and isn''t stored. What is stored is the _number_ of integers that equal that indice.
- mongrelprogrammer
introspective or introsort does a quicksort but can determine whether the input is an (almost) worst case scenario and will then switch to an O(n*log(n)) algorithm (mergesort I think). This is what STLport''s std::sort does IIRC.
Regards,
Dirk Gerrits
Regards,
Dirk Gerrits
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement