Radix Sort Java

Question

Welcome. I have a radix sorting method that uses an array to go through, but has to have another array (bin) that will store in an empty queue. I am confused as to how I would make a queue for the bins. I also have a findPlace method that finds the place of the each digit when called upon. So, here is what I got. Can someone help me find what I am missing? Thanks so much for your time.

public static void radix(int [] list){
       int [] bin = new int[10]; 
      ArrayQueue<Integer> part = new ArrayQueue<Integer>(); // EDIT What would I do with this queue?? 
      int num = 0; 
         for(int i=0;i<list.length;i++)
         {
            bin[i] = 0;  
          }

            for(int pass=0;pass<list.length;pass++)
           {
                for(int num=0;num<list.length;num++)
               {
                       int digit=findPlace(bin[pass], num);
                 }

                  bin[digit].add(list[num]); // add to the bin
            }
              // Put back into list
               for(int h=0; h<10; h++)
               {
                    while(!bin[h].isEmpty())
                    {
                       list[num] = bin[queueNum].remove();
                     num++;
                    }
              }
        }


public static int getPlace (int x, int place)
    {return x/place % 10;}

I also made a method to find the bucket, So i just need to know how I would put it into an array, would I just do this? part.add(getPlace(x, place));?

Answer 1

Your array, bin doesn't act like a queue just because you want it to :) Arrays don't have methods like add() and remove(). You have two choices on how to fix this:

• Program in the proper handling for queues yourself: A queue consists of an array and two pointers into that array, traditionally called head and tail. You'd have to write your own methods to add and remove, which would work with the array and the pointers and take care of an empty queue or an overflowing one.

• Use Java's built-in Queue class. It's documented in the library's Javadocs. Don't know if your assignment intends for you to build your own queue, though.

Update with another detail:

You asked how to extract a single digit from a number. It's easiest working from the least significant digits (LSD) as suggested in the Wikipedia article. To do that:

• To extract the last digit, do digit = number % 10 (that's the modulo operation). You will get an integer between 0 and 9 inclusive.
• To strip off the last digit, simply divide by 10. Then you can pull off another digit.
• Since you'll need to be looking at the n-th last digit of a number several times, you would do well to put this functionality into a separate method.

You can use your 0 thru 9 to select the right queue to put your number on.

When you've finished queueing all your numbers into the 10 buckets, you need to copy them from there back into a single list. Then repeat as long as there are still digits in any number that you haven't processed.