Archived

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

Waverider

Questions about radix sort

Recommended Posts

Waverider    169
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
Waverider    169
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