Sign in to follow this  
Halsafar

Radix Sort Q

Recommended Posts

I'm reading up on the RADIX sort method since it is the fastest I know of. Now after reading a few articles of research it has been proven that the fastest method if of course the 256 - BYTE SORT METHOD as described in this articles: http://www.gamedev.net/reference/articles/article410.asp I follow along just fine, the sorting method makes somewhat sense, I am interested to start coding one but I have one place of major concern. If I can only sort values 0-256 then em I limited to array's of 256? I am quite confused on this point, especially since the author says he uses's the 256 method to sort 10 to 10,000 polygons. Personally I'll have tons of particles to sort every time a new one is injected and it is not able to slide in at the beginning or the end of the buffer. I have to do manual zbuffering since Alpha blending + GoRaudShade + ZbufferOn = Very ugly look

Share this post


Link to post
Share on other sites
The fastest method depends on the problem. But radix sort should be a good general fit for this kind of sorting. (Bubble is faster than radix on presorted data for example)

But for your question you can sort sort more 256 numbers. He's just using a byte for a radix instead of a bit (like in the BASE 2 RADIX SORT). He basically sorts by the least significant byte, then the next least significant byte, and so on until the most significant byte. So for sorting 32bit (4byte) integers, you sort the data 4 times, once for each byte.

Share this post


Link to post
Share on other sites
The textbook for my digital systems class claims that while radix sort looks faster than qsort on paper, you have to really look out for cache misses since they will ruin your performance. Qsort does better in practice for data sets that are prone to cache misses because it has better temporal coherence.

Of course this was from a discussion of classic radix sort. You might do better with a revised algorithm (or not).

My 2c.

Share this post


Link to post
Share on other sites
QSort is the best (single-threaded) algorithm there is for sorting arbitrarily ordered data without any restrictions. (nothing can be faster than O(n*log(n)) for non-sorted elements) (I believe there are mergesorts that are slightly faster in their best case, but they are overly optimized and so hacked into oblivion that it is not worth going for them)

Radix if I'm not mistaken "is" faster because of the fact, that there is an invariant that needs to be met... which is, you must know in which range your elements are in, meaning, that you no longer sort, but group, as you are expecting 10 groups, but have e.g. 1000 elements, this can be done in one go. But then you must only have index from 0-9 too, so this would perhaps be useful for sorting by shaders (the same shade is commonly used many many times).

(the only real use for bubblesort, or the prefered insertionsort is when you have a sorted list with VERY FEW unsorted elements, that is, perhaps 1-4 in 10000 elements, but then again, if that wouldn't be the case your screwed... big time)

EDIT: as the text says, nothing can actually have lower complexity than O(n*log(n)), just make less passes or do them faster (such as msort/qsort). All other sorting techniques rely on very strong/unusual invariants.

Share this post


Link to post
Share on other sites
You are mistaken. Radix sort is O(n). Saying that it's not a sort is silly. But complexity is not the only thing that determines sort performance (caching, in particular, matters). That was my point.

Share this post


Link to post
Share on other sites
Well in a way you are wrong, because Radix is not sorting per definition, as I said, it requires a very strong invariant which can only be satisfied in very few cases, that is, when you have many many elements, but only a few unique, you cannot sort arbitrary data with it. So really, one cannot even compare Radix and Qsort.

EDIT: e.g. you cannot sort a phonebook using radix.

Share this post


Link to post
Share on other sites
Sure I can. Just turn the names into base 27 numbers, with each letter representing a digit and the space character representing a digit.

Share this post


Link to post
Share on other sites
Trust me on this one, I've gone courses on it.

Quote from the Radix paper
"That’s why this sort routine breaks the theoretical lower bound of the O(N*logN) complexity"

with other words, nothing can _SORT_ faster than O(n*log(n))

How come Radix can? Because it isn't comparing or sorting, it is _grouping_ data, and to do that it needs a predefined number of groups.

In your case you would have base 27 right? Yes you can sort on that... but let's see what happens

if you want a 10 character limit, you will get 27^10 as the number of groups (all possible strings with 10 characters at most in it)... 205891132094649 ... oh dear, that's quite the number... let's see, and then multiply by AT LEAST 4 bytes per pointer (should be more for counting etc) 823564528378596 ... hmm, that is 823TB of memory needed (without the strings) ...

And indeed, regardless of sorting 1 string, or 2 strings, you would still have to traverse the ENTIRE list to get the sorted list out... which would pretty much take forever. (and still we have a 10 letter limit)

Do you still think you can _SORT_ with radix?
No you cannot, what you for instance CAN do however is to Radix sort by the first letter, and then Qsort the groups, don't know if there is any gain though.

As the text says, and the mathematicians says, "nothing can _SORT_ faster than O(n*log(n))", it has been mathematically proven, however, you can group data faster.

Which is what Radix does, the condition for usage of radix is like grouping all the worls people by age, as you would have about 100 groups, and many million people it would be extremely fast, but not sorting a phonebook, because there is no group limit, and also no use of it.

Sorting arbitrary data is best done using qsort/msort.
Sorting very limited range data is best done using Radix.

EDIT: in regard to the initial post, sorting tens of thousands of polygons using RADIX is very likely done using approximation, meaning, you round the distance off to only cover a small area e.g. 0-255, thus getting vicious speed, and decent sorting, but not perfect, but good enough to be used by the GPU to draw them in almost front-to-back order.

[Edited by - Syranide on June 29, 2005 7:10:56 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Halsafar : If sorted insertion is needed and you don't create too many particles by frame, you should consider using heaps.
Each insertion/removal is in O(log N)

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Halsafar : If sorted insertion is needed and you don't create too many particles by frame, you should consider using heaps.
Each insertion/removal is in O(log N)


I would actually say Qsort is better, QuickSort is better than HeapSort, and because we are not expecting to get any data from the heap before we have inserted it all, the point of the Hsort is lost and Qsort would perform better.

(The only thing that justifies Heaps instead of Qsort is the usage as a queue, in other areas Heaps/HeapSort performs worse. And since we are working with a buffer, we have no use of a queue)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this