Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

willis3000

Sorting Algorithms

This topic is 5891 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
The answer isn''t as simple as that. The answer depends on what you are trying to sort and what you already know about the data.

Although there has been some research developments in this field recently I don''t know about here is what I suggest:

In case you need to sort objects that has fairly few values (say the set of integers) then radix-sort, bucket-sort, and distribution-sort is the fastest. (These algorithms can sort in linear time!)

Otherwise, the sort algorithms with the best worst-case is heap-sort and merge-sort. Heap-sort is probably a bit slower than merge sort but has the advantage that the sort can be done in place very easily.

However, if you want to optimize for the best average sorting time quick-sort is best - but quick sort performs very poorly in some cases.

Insertion sort (of which Shell''s sort is a varient), bubble sort, etc. are slow and should be avoided if you need high speed.

Share this post


Link to post
Share on other sites
Well, it depends on the order of your data.

The ones I use most extensively and seem to do wonders for me are quicksort and merge sort. They are both O(n log n) if the data is "good", and O(n2) if the data is "bad."

The quicksort is the faster of the two, and the merge sort uses a more than double the memory (due to the second array). They are both recursive, so that could be a con or a pro depending on who (or what) taught you how to program, but they both can be implemented in a non-recursive fashion though it doesn't yield any significant improvement on most machines.

The quicksort is the most practical sort function, but there are others such as the heap sort that are better than the quicksort for extremely large (around 107+ (dependent on the machine of course) items. [Edit] There are others that are better for small data sets too. But, for the best overall performance I'd stick with the quicksort.

[edited by - Floppy on June 1, 2002 7:27:00 PM]

Share this post


Link to post
Share on other sites
>> and merge sort. They are both O(n log n) if the data is "good", and O(n2) if the data is "bad."

No, the worst case of merge sort is O(n log n).

I want to put attention to the radix-sort algorithm (and the related algorithms) since it has a worst case complexity of O(n).

And for a really fast number sorting algorithm check out this article:
http://www.marner.dk/Nilsson.pdf

[edited by - felonius on June 1, 2002 8:09:30 PM]

Share this post


Link to post
Share on other sites
Those (Quick, Merge, Shell, etc) algorithms belong to the past...
Dont you remember that now we have BS Sort, that is probably something like O(1)? Ha...


Cya,
-RoTTer

Share this post


Link to post
Share on other sites
I''d like to point out that although radix sort is linear, if you actually analyze it you''ll see that radix sort will only be faster than O(nlogn) if there are are more elements than there are values. (eg. If you are sorting bytes (value: 0..255) then you need to be sorting more than 256 bytes in order for radix sort to be faster than qsort).

Give a man a fish and you feed him for a day; teach him to use the Net and he won''t bother you for weeks.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Insertion sort is fast for data that''s almost in order already. Some people implement Quicksort so that after the chunks are small enough (like, less than 4 elements), it sorts the array with insertion sort.

Of the simple algorithms, bubble sort is something everyone should avoid though.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!