RADIX SORTING TUTOR
Version 1
jmX Opiate
Introduction
Well, many of you may already know what radix sorting is and how it is
done, but for those of you who dont, this tutor is for you. I just recently
found out how it was done, so I am no expert on it but it is a fairly simple
concept and ill do my best to present it as one. Lets get started.
What is it?
Radix sorting is a method of sorting numbers without using compares ie ,
, , cmp, etc... It is that fact that makes it one of the fastest sorting
routines out there for sorting a list of numbers. As far as I know, some of
the fastest 3d engines out there use radix sorting when dynamic 3d data is
being used. If your data is static ie...walls in a dungeon ala doom then
BSP trees are the way to go as far as that data is concerned. But, if your
objects are moving around and morphing, then radix is a good way to sort.
How its done
The radix sorting I will talk about in this doc is done on the BIT level.
We will sort a list of numbers by looking at the seperate bits that make up
a number. To understand how it works, you must understand binary numbers -
which Im sure we all do.
Ill explain it the way I was taught.....with a concept of buckets. Lets
say we have a list of 4 8-bit numbers. First, what we do is look at the least
important bit of each number. This is either 1 or 0. We put all the 1s in
one bucket and all the 0s in another. Now, we merge the 2 with the 0s
bucket appearing first. Now, use the 2nd least significant bit and resort
back into the 1s and 0s buckets, then merge with the 0s bucket first.
After we do this 8 times for 8 bit nums we will have a sorted list. It
is just that simple. I hear some of you saying buckets? wtf! ok..well, that
is understandable, so let me show you an example.
Example
Lets say we have a list of 8 numbers:
Decimal Binary
23 00010111
184 10111000
7 00000111
253 11111101
105 01101001
217 11011001
89 01011001
166 10100110
First what well do is use the LSB Least Significant Bit or rightmost bit
to determine if the number goes into the 1s or 0s bucket or list. We just
go down the top of the list and go to the end...makes sense eh? Here are the
2 buckets after we separate them for the first time. I will use the binary
versions of the numbers until we have finished sorting. Ill put an asterisk
above the bit we are curently looking at.
0s Bucket 1s Bucket
10111000 00010111
10100110 00000111
11111101
01101001
11011001
01011001
Now, we merge the 2 lists into one, with the 0s bucket going first.
Merged List after BIT 0 pass
10111000 10100110 00010111 00000111 11111101 01101001 11011001 01011001
Now, we repeat the whole process over for the 2nd least significant bit, or
the second bit from the right. Again, its important that we do this in order
of our merged list, going from the top down.
0s Bucket 1s Bucket
10111000 10100110
11111101 00010111
01101001 00000111
11011001
01011001
Merged List after BIT 1 pass
10111000 11111101 01101001 11011001 01011001 10100110 00010111 00000111
Ok, now the 3rd bit. Gee, this is tiring.
0s Bucket 1s Bucket
10111000 11111101
01101001 10100110
11011001 00010111
01011001 00001111
Merged List after 3rd pass
10111000 01101001 11011001 01011001 11111101 10100110 00010111 00001111
4th PASS. 4th bit from the right.
0s Bucket 1s Bucket
10100110 10111000
00010111 01101001
11011001
01011001
11111101
00001111
Merged List after 4th pass
10100110 00010111 10111000 01101001 11011001 01011001 11111101 00001111
5th PASS. 5th bit from the right.
0s Bucket 1s Bucket
10100110 00010111
01101001 10111000
00001111 11011001
01011001
11111101
Merged List after 5th pass
10100110 01101001 00001111 00010111 10111000 11011001 01011001 11111101
Now it is time to go get a soda and some cookies.
ONLY 3 MORE TO GO!
6th PASS. 6th bit from the right.
0s Bucket 1s Bucket
00001111 10100110
00010111 01101001
11011001 10111000
01011001 11111101
Merged List after 6th pass
00001111 00010111 11011001 01011001 10100110 01101001 10111000 11111101
7th PASS. 7th bit from the right.
0s Bucket 1s Bucket
00001111 11011001
00010111 01011001
10100110 01101001
10111000 11111101
Merged List after 7th pass
00001111 00010111 10100110 10111000 11011001 01011001 01101001 11111101
FINAL PASS!!!!! 8th bit from the right, or the first bit on the left
0s Bucket 1s Bucket
00001111 10100110
00010111 10111000
01011001 11011001
01101001 11111101
Merged List after FINAL pass
00001111 7
00010111 23
01011001 89
01101001 105
10100110 166
10111000 184
11011001 217
11111101 253
Whew! IT WORKED!
Ok, now that you see how the example worked you may be saying geez, that
was a lot of work, how is this faster than other sorting methods? First off,
this method uses NO COMPARING. That is one of the most important issue. Also,
some soring techniques slow down logarithmicly with the number of objects you
are sorting. Radix sorting loops increase linearly with the number of objects
you sort, so, for large or lengthy lists you will see a large speed increase.
How to implement in code
Here is a sample implementation. It is simple, and it pre allocated 2 buckets
that were large enough to hold all the numbers in the main list if needed.
Other versions may use linked lists to save on memory usuage.
Listsize is the length of the list of numbers to be sorted. The List array
is the area that holds the merged list, and bucket0 and bucket1 are the 2
temporary buckets we discussed earlier.
for pass0pass7pass++
bitmask1pass
bucket0index0
bucket1index0
for x0xlistsizex++
if listx mask bucket1bucket1index++listx
else bucket0bucket0index++listx
Conclusion
I hope by now you have the knowledge you need to get your own radix sorting
routines to work. I am sick of typing about it, and Im sure you are sick of
reading about it so go sort some of your own numbers now!
-jmX / Opiate / Kosmic
EMAIl: jmX@ix.netcom.com
Version 1
jmX Opiate
Introduction
Well, many of you may already know what radix sorting is and how it is
done, but for those of you who dont, this tutor is for you. I just recently
found out how it was done, so I am no expert on it but it is a fairly simple
concept and ill do my best to present it as one. Lets get started.
What is it?
Radix sorting is a method of sorting numbers without using compares ie ,
, , cmp, etc... It is that fact that makes it one of the fastest sorting
routines out there for sorting a list of numbers. As far as I know, some of
the fastest 3d engines out there use radix sorting when dynamic 3d data is
being used. If your data is static ie...walls in a dungeon ala doom then
BSP trees are the way to go as far as that data is concerned. But, if your
objects are moving around and morphing, then radix is a good way to sort.
How its done
The radix sorting I will talk about in this doc is done on the BIT level.
We will sort a list of numbers by looking at the seperate bits that make up
a number. To understand how it works, you must understand binary numbers -
which Im sure we all do.
Ill explain it the way I was taught.....with a concept of buckets. Lets
say we have a list of 4 8-bit numbers. First, what we do is look at the least
important bit of each number. This is either 1 or 0. We put all the 1s in
one bucket and all the 0s in another. Now, we merge the 2 with the 0s
bucket appearing first. Now, use the 2nd least significant bit and resort
back into the 1s and 0s buckets, then merge with the 0s bucket first.
After we do this 8 times for 8 bit nums we will have a sorted list. It
is just that simple. I hear some of you saying buckets? wtf! ok..well, that
is understandable, so let me show you an example.
Example
Lets say we have a list of 8 numbers:
Decimal Binary
23 00010111
184 10111000
7 00000111
253 11111101
105 01101001
217 11011001
89 01011001
166 10100110
First what well do is use the LSB Least Significant Bit or rightmost bit
to determine if the number goes into the 1s or 0s bucket or list. We just
go down the top of the list and go to the end...makes sense eh? Here are the
2 buckets after we separate them for the first time. I will use the binary
versions of the numbers until we have finished sorting. Ill put an asterisk
above the bit we are curently looking at.
0s Bucket 1s Bucket
10111000 00010111
10100110 00000111
11111101
01101001
11011001
01011001
Now, we merge the 2 lists into one, with the 0s bucket going first.
Merged List after BIT 0 pass
10111000 10100110 00010111 00000111 11111101 01101001 11011001 01011001
Now, we repeat the whole process over for the 2nd least significant bit, or
the second bit from the right. Again, its important that we do this in order
of our merged list, going from the top down.
0s Bucket 1s Bucket
10111000 10100110
11111101 00010111
01101001 00000111
11011001
01011001
Merged List after BIT 1 pass
10111000 11111101 01101001 11011001 01011001 10100110 00010111 00000111
Ok, now the 3rd bit. Gee, this is tiring.
0s Bucket 1s Bucket
10111000 11111101
01101001 10100110
11011001 00010111
01011001 00001111
Merged List after 3rd pass
10111000 01101001 11011001 01011001 11111101 10100110 00010111 00001111
4th PASS. 4th bit from the right.
0s Bucket 1s Bucket
10100110 10111000
00010111 01101001
11011001
01011001
11111101
00001111
Merged List after 4th pass
10100110 00010111 10111000 01101001 11011001 01011001 11111101 00001111
5th PASS. 5th bit from the right.
0s Bucket 1s Bucket
10100110 00010111
01101001 10111000
00001111 11011001
01011001
11111101
Merged List after 5th pass
10100110 01101001 00001111 00010111 10111000 11011001 01011001 11111101
Now it is time to go get a soda and some cookies.
ONLY 3 MORE TO GO!
6th PASS. 6th bit from the right.
0s Bucket 1s Bucket
00001111 10100110
00010111 01101001
11011001 10111000
01011001 11111101
Merged List after 6th pass
00001111 00010111 11011001 01011001 10100110 01101001 10111000 11111101
7th PASS. 7th bit from the right.
0s Bucket 1s Bucket
00001111 11011001
00010111 01011001
10100110 01101001
10111000 11111101
Merged List after 7th pass
00001111 00010111 10100110 10111000 11011001 01011001 01101001 11111101
FINAL PASS!!!!! 8th bit from the right, or the first bit on the left
0s Bucket 1s Bucket
00001111 10100110
00010111 10111000
01011001 11011001
01101001 11111101
Merged List after FINAL pass
00001111 7
00010111 23
01011001 89
01101001 105
10100110 166
10111000 184
11011001 217
11111101 253
Whew! IT WORKED!
Ok, now that you see how the example worked you may be saying geez, that
was a lot of work, how is this faster than other sorting methods? First off,
this method uses NO COMPARING. That is one of the most important issue. Also,
some soring techniques slow down logarithmicly with the number of objects you
are sorting. Radix sorting loops increase linearly with the number of objects
you sort, so, for large or lengthy lists you will see a large speed increase.
How to implement in code
Here is a sample implementation. It is simple, and it pre allocated 2 buckets
that were large enough to hold all the numbers in the main list if needed.
Other versions may use linked lists to save on memory usuage.
Listsize is the length of the list of numbers to be sorted. The List array
is the area that holds the merged list, and bucket0 and bucket1 are the 2
temporary buckets we discussed earlier.
for pass0pass7pass++
bitmask1pass
bucket0index0
bucket1index0
for x0xlistsizex++
if listx mask bucket1bucket1index++listx
else bucket0bucket0index++listx
Conclusion
I hope by now you have the knowledge you need to get your own radix sorting
routines to work. I am sick of typing about it, and Im sure you are sick of
reading about it so go sort some of your own numbers now!
-jmX / Opiate / Kosmic
EMAIl: jmX@ix.netcom.com
log in to add a comment.