Radix Sort Algorithm

Question

I have been given some algorithms to reverse engineer. The algorithm below is a radix sort, but I am very confused about what is actually happening in the code.

I'm new to algorithms and am unsure how the code sorts elements in an array. I'm not sure what bits have to do with the algorithm and what a mask is. Here is the code:

    ArrayList<Integer> array = CopyArray(a);
    Integer[] zerobucket = new Integer[a.size()];
    Integer[] onebucket = new Integer[a.size()];
    int i, bit;
    Integer element, mask;

    for (bit=0; bit<8; ++bit) {
        int zc = 0;
        int oc = 0;

        for(i=0; i<array.size(); ++i) {
            element = array.get(i);
            mask = 1 << bit;
            if ((element & mask) == 0) {
                zerobucket[zc++] = array.get(i);
            } else {
                onebucket[oc++] = array.get(i);
            }
        }
        for(i=0; i<oc; ++i) array.set(i,onebucket[i]);
        for(i=0; i<zc; ++i) array.set(i+oc,zerobucket[i]);
    }
    return(array);

Avoid Integer. They are slow and waste memory. Use int.

Has QUIT--Anony-Mousse
– Has QUIT--Anony-Mousse

2015-01-02 17:27:52 +00:00
Commented Jan 2, 2015 at 17:27 — Has QUIT--Anony-Mousse
– Has QUIT--Anony-Mousse, Commented Jan 2, 2015 at 17:27

ErstwhileIII · Accepted Answer · 2015-01-02 16:09:22Z

3

Algorithms are where you should start learning about programming!

To see what an undocumented piece of code does, you may need to adopt a pseudo-language to put the work into an english mathematics statement.

For example, you note that this snippet should only work for 8-bit numbers (the outer loop on bit). The rough description is that the array elements are "sorted" into two buckets depending on whether the bit in position "bit" is a zero or a one -- starting with the bit in the lease significant position. The original array is then reordered with "ones" coming before "zeros" .. which should order the array from largest to smallest.

You would be well served to look up radix sort algorithms, and start with that rather than starting with code.

edited Jan 2, 2015 at 16:09

answered Jan 2, 2015 at 16:03

ErstwhileIII

4,8722 gold badges25 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jobs · Accepted Answer · 2015-01-02 17:23:47Z

Your algorithm works for 8 bit numbers, and you are looking at one bit at a time. An easier to understand example is the following, using decimal instead of binary.

Sort on 1s:    771 721 822 955 405   5 925 825 777  28 829
Sort on 10s:   405   5 721 822 925 825  28 829 955 771 777
Sort on 100s:    5  28 405 721 771 777 822 825 829 925 955

After we sort on the middle digit, observe that the numbers are sorted by their last two digits. After we sort on the most significant digit, the numbers are completely sorted.

The same goes for binary. The number of buckets we're using to sort is the SAME as the radix of the digit we use as a sort key during one pass of bucket or counting sort. "Radix" is a synonym for the base of a number, hence the name "radix sort." In your example, the number is 2.

Floegipoky · Accepted Answer · 2015-01-02 16:12:14Z

0

A mask, or bitmask, is used to "turn off" every bit except those that are allowed to be "seen" through the mask. The 0s filter out the bit they are ANDed with, the 1s allow the bit through. A common usage is to isolate a byte-sized portion of an integer data type:

00000000 11111111 00000000 00000000
& // Boolean AND
10010101 10010101 10010101 10010101
yields
00000000 10010101 00000000 00000000

answered Jan 2, 2015 at 16:12

Floegipoky

3,3011 gold badge34 silver badges48 bronze badges

2 Comments

ErstwhileIII Over a year ago

While this information is true, it does not get to the heart of the problem on how to discern or describe the algorithm implemented by a set of code.

Solomon Slow Over a year ago

@floegipoky, true, this "answer" does not answer the whole question, but it does answer the part where the OP said, "I'm not sure [...] what a mask is"

Goutham nagraj · Accepted Answer · 2015-01-17 15:39:05Z

0

/*try this iterative method and 100% working*/
    #include<stdio.h>
    #include<math.h>
    int sort();
    int display();
    long int a[20],n;
    int main(){
    int i;
    printf("enter the size:");
    scanf("%d",&n);
    printf("\nenter the array elements\n");
          for(i=0;i<n;i++){scanf("%d",&a[i]);}
             sort();
   return 0;
          }

int sort()
{
int p=0,rad[20],q,s=0,i=0;
int k1,k2,t; 
while(p<=3)
     {
q=0;
          while(q<=9)
               {
                 i=0;
          while(a[i]!='\0')
               {
                 t=pow(10,(p+1));
                 k1=a[i]%t;
                 k2=k1/pow(10,p);

          if(k2==q) {rad[s]=a[i];s++;}
             i++;
                }
         q++;
                }
 s=0;
 printf("\n sort for %dth\n",p);
 for(i=0;i<n;i++){a[i]=rad[i];}
 printf("\n");
  display();
 p++;
       }
return 0;
       }    

int display(){
int i=0;
while(a[i]!='\0')
 {
printf("%d\t",a[i]);
i++;
 }
return 0;
              }

answered Jan 17, 2015 at 15:39

Goutham nagraj

1

1 Comment

Goutham nagraj Over a year ago

In the output sort for 0, 1,2,3,4 means units tens hundreds thousands

Collectives™ on Stack Overflow

Radix Sort Algorithm

4 Answers 4

Comments

Comments

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related