• 06-14-2010
kraghavan
Hi all, Im trying to learn radix sorting here. I found this nice sample code. While trying to undestand the code i have a few doubts.
Can you explain what the coder has done?
Code:

```#include <iostream.h> #include <stdlib.h> #include <string.h> void radix (int byte, long N, long *source, long *dest) {   long count[256];   long index[256];   memset (count, 0, sizeof (count));   for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;   index[0]=0;   for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];   for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i]; // Doubt 1. } void radixsort (long *source, long *temp, long N) {   radix (0, N, source, temp);   radix (1, N, temp, source);   radix (2, N, source, temp);   radix (3, N, temp, source); } void make_random (long *data, long N) {   for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16); } long data[100]; long temp[100]; void main (void) {   make_random(data, 100);   radixsort (data, temp, 100);   for ( int i=0; i<100; i++ ) cout << data[i] << '\n'; }```
In function radix i have marked the dount. Can you explain why the coder has used this sentence"?
for ( i=0; i<N; i++ )
{
dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

in particular - whats right shift operator doing and why is & doing here .. which is incremented here?
would help me understand it better
thank
regards
KR
• 06-14-2010
Salem
Why not split it out into several statements?

Code:

```temp = ((source[i])>>(byte*8))&0xff; dest[index[temp]++] = source[i];```
Then you can at least print the sub-expressions and learn what is going on.
• 06-15-2010
kraghavan
thanks i tried that.. all i need to know is how is he sorted the numbers using the shift operators and & instead of using place value notation in this sorting...
i hope you understood what im saying... i would be greatful if some1 explained..
thanks
regards,
KR
• 06-15-2010
Salem
> (source[i])>>(byte*8)

If source[i] contains say 0x12345678, then depending on the value of byte, you would get 0x12, 0x34, 0x56 or 0x78.

The &0xff is to ensure that the result is just one byte.
0x12345678 >> 8 is 0x00123456.
Masking with 0xff leaves you with just 0x56

Exactly how/why this implements a radix sort is another matter.