🔒 Locked

got_radix?

Started by silvermace Oct 4, 2002 at 8:22 AM 4 replies 300+ views

Original Post

105

Oct 4, 2002 at 8:22 AM

im having alot of trouble understanding how the good ol radix sort works .. manily because all i get is a "pie-o-code" in the face, i am a visual learner and i would really like to understand why & how radix works, diagrams etc. what im trying to do is sort poly''s according to their texture names (an Unsigned Integer) to reduce the number of texture binds & state changes made. thanx 4 the help

laterz /silvermace

 ^^^
do.Ob
 [-]
  ^

Waverider

108

Waverider

Oct 4, 2002 at 9:52 AM

Here's a visual for you.

Take a bunch of random numbers from 1 to 999. They will have 3 digits, so we will make 3 passes (one for the 1's digit, 10's digit and 100's digit respectively)

Since there are ten values possible for a digit (0-9), we need ten bins. So take ten buckets and label them 0 thru 9. Line them up from 0 to 9 in sequence.

Ok, now, take all your random numbers, look at the 1's digit, and toss them in the bucket that is named that digit.

Now go from bucket 0 to 9 in order, and look at the numbers in each bucket in the order you put them there, and toss them in the bucket that matches the 10's digit.

Now do it again for the 100's digit.

Now if you go from bucket 0 to 9 and look at each number in the order you placed them there on the 100's pass, you'll find they are perfectly sorted.

How's that for visual?

If you are sorting unsigned integers, then you could treat each byte as a "digit", which has a possible value of 0-255, meaning you'll need 256 bins. And since unsigned integers are composed of two bytes, you will make 2 passes to sort them.

Here's one link I got from yahoo on "Radix Sort": Radix Sort Tutorial

[edited by - Waverider on October 4, 2002 11:05:57 AM]

silvermace

Author

105

silvermace

Oct 4, 2002 at 8:19 PM

Thanx !
but, how do i access the "sig figure" in the digit, im guessing through a little tactical bitshifting & pointer arithmatic ?

thanx for the help so far, its great !

Waverider

108

Waverider

Oct 4, 2002 at 8:33 PM

"sig figure"?

You mean, how do you extract the digit itself?

In C, if you are sorting unsigned ints using the 256-bin method, you can access the bytes like this:

unsigned int uValue;
unsigned char *ptr;
ptr = (unsigned char *)&uValue

sort first on *(ptr), then sort on *(ptr + 1)

You would think that you would sort on *(ptr + 1) first, BUT... C stores the least significant byte in the first byte, not the second.

If you want to access a 1's, 10's and 100's digit for the 1-999 example, that will require some division operations.

[edited by - Waverider on October 4, 2002 9:34:18 PM]

silvermace

Author

105

silvermace

Oct 6, 2002 at 1:20 AM

thanx for that!

is there a way to print out that digit ?
(for learnings sake)

  
// would this work ? 

// it just prints 0

uint udata = 25;
byte *bdata = (byte*) &udata
uint h1 = ((uint) *(bdata+1));
cout << h1 << endl;

[edited by - silvermace on October 6, 2002 2:25:44 AM]

Waverider

108

Waverider

Oct 7, 2002 at 5:28 PM

If you output *(bdata), it should print out 25.

25 as an unsigned integer is stored in memory as 25,0.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.