Jump to content
  • Advertisement

Archived

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

Waverider

Questions about radix sort

This topic is 5767 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

Okay, I've been reading up on sort algorithms... Bubble sort makes it quickly through a nearly sorted list, but performs badly with arbitrary data. O(n^2) Quicksort does well with arbitrary data, but performs badly with nearly sorted lists. O(n log(n)) Radix sort seems to be a constant animal. It always makes the same number of passes no matter what. O(kn) I read an article that suggested casting float values to integer by pointing to the memory location with an integer pointer. Using this method, you can perform a radix sort on float values by extracting the bytes on each pass. Fascinating. In this case, k = 4, for four bytes of data to sort throughout 256 bins, right? My main question is this - I've heard it said that radix sort is the best for game sorting. If the list is nearly sorted already, how would I speed up the algorithm? Or does this algorithm ALWAYS have the same number of passes, as the article suggests? [edited by - Waverider on October 2, 2002 8:32:33 PM]

Share this post


Link to post
Share on other sites
Advertisement
Well, I'm figuring that if I let the algorithm run through as is, I would re-sort into bins on the last byte, then the third, then second, then first.

The problem is on a nearly sorted list, arranging on the last byte will just mess them all up again, forcing the algorithm to go through all its iterations.

The only way I can think to speed it up is just check the list for anything to be out of order, and if they are already sorted, then just don't run the algorithm.

Is there a shortcut I'm missing?

[edited by - Waverider on October 2, 2002 8:55:46 PM]

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!