Radix sort in java help

Hi i need some help to improve my code. I am trying to use Radixsort to sort array of 10 numbers (for example) in increasing order.

When i run the program with array of size 10 and put 10 random int numbers in like 70 309 450 279 799 192 586 609 54 657

i get this out:

450 309 192 279 54 192 586 657 54 609

Don´t see where my error is in the code.

class IntQueue
{

  static class Hlekkur
  {
    int tala;
    Hlekkur naest;
  }

  Hlekkur fyrsti;
  Hlekkur sidasti;
  int n;

  public IntQueue()
  {
    fyrsti = sidasti = null;
  }


  // First number in queue.
  public int first()
  {
    return fyrsti.tala;
  }


  public int get()
  {
    int res = fyrsti.tala;
    n--;
    if( fyrsti == sidasti )
      fyrsti = sidasti = null;
    else
      fyrsti = fyrsti.naest;
    return res;
  }


  public void put( int i )
  {
    Hlekkur nyr = new Hlekkur();
    n++;
    nyr.tala = i;
    if( sidasti==null )
    f yrsti = sidasti = nyr;
    else
    {
      sidasti.naest = nyr;
      sidasti = nyr;
    }
  }


  public int count()
  {
    return n;
  }

  public static void radixSort(int [] q, int n, int d){
    IntQueue [] queue = new IntQueue[n];

    for (int k = 0; k < n; k++){
      queue[k] = new IntQueue();
    }
    for (int i开发者_StackOverflow社区 = d-1; i >=0; i--){
      for (int j = 0; j < n; j++){
        while(queue[j].count() != 0)
        {
          queue[j].get();
        }
      }
      for (int index = 0; index < n; index++){
        // trying to look at one of three digit to sort after.
        int v=1;
        int digit = (q[index]/v)%10;
        v*=10;

        queue[digit].put(q[index]);
      }
      for (int p = 0; p < n; p++){
        while(queue[p].count() != 0) {
          q[p] = (queue[p].get());
        }
      }
    }
  }
}

I am also thinking can I let the function take one queue as an argument and on return that queue is in increasing order? If so how?

Please help. Sorry if my english is bad not so good in it.

Please let know if you need more details.

import java.util.Random;
public class RadTest extends IntQueue {

    public static void main(String[] args)
    {
        int [] q = new int[10];
        Random r = new Random();
        int t = 0;
        int size = 10;
        while(t != size)
        {
            q[t] = (r.nextInt(1000));
            t++;
        }

        for(int i = 0; i!= size; i++)
        {
            System.out.println(q[i]);
        }

        System.out.println("Radad: \n");
        radixSort(q,size,3);

        for(int i = 0; i!= size; i++)
        {
            System.out.println(q[i]);
        }

    }
}

Hope this is what you were talking about...

Thank you for your answer, I will look into it. Not looking for someone to solve the problem for me. Looking for help and Ideas how i can solve it.

in my task it says:

Implement a radix sort function for integers that sorts with queues. The function should take one queue as an argument and on return that queue should contain the same values in ascending order You may assume that the values are between 0 and 999.

Can i put 100 int numbers on my queue and use radixsort function to sort it or do i need to put numbers in array and then array in radixsort function which use queues?

I understand it like i needed to put numbers in Int queue and put that queue into the function but that has not worked.

But Thank for your answers will look at them and try to solve my problem. But if you think you can help please leave comment.

This works for the test cases I tried. It's not entirely well documented, but I think that's okay. I'll leave it to you to read it, compare it to what you're currently doing, and find out why what you have might be different than mine in philosophy. There's also other things that are marked where I did them the "lazy" way, and you should do them a better way.

import java.util.*;
class Radix {

    static int[] radixSort(int[] arr) {
        // Bucket is only used in this method, so I declare it here
        // I'm not 100% sure I recommend doing this in production code
        // but it turns out, it's perfectly legal to do!
        class Bucket {
            private List<Integer> list = new LinkedList<Integer>();
            int[] sorted;

            public void add(int i) { list.add(i);  sorted = null;}

            public int[] getSortedArray() {
                if(sorted == null) {
                    sorted = new int[list.size()];
                    int i = 0;
                    for(Integer val : list) {
                        sorted[i++] = val.intValue(); // probably could autobox, oh well
                    }
                    Arrays.sort(sorted); // use whatever method you want to sort here... 
                                         // Arrays.sort probably isn't allowed
                }
                return sorted;
            }
        }

        int maxLen = 0;
        for(int i : arr) {
            if(i < 0) throw new IllegalArgumentException("I don't deal with negative numbers");
            int len = numKeys(i);
            if(len > maxLen) maxLen = len;
        }

        Bucket[] buckets = new Bucket[maxLen];

        for(int i = 0; i < buckets.length; i++) buckets[i] = new Bucket();
        for(int i : arr) buckets[numKeys(i)-1].add(i);

        int[] result = new int[arr.length];
        int[] posarr = new int[buckets.length]; // all int to 0

        for(int i = 0; i < result.length; i++) {
            // get the 'best' element, which will be the most appropriate from
            // the set of earliest unused elements from each bucket
            int best = -1;
            int bestpos = -1;
            for(int p = 0; p < posarr.length; p++) {
                if(posarr[p] == buckets[p].getSortedArray().length) continue;
                int oldbest = best;
                best = bestOf(best, buckets[p].getSortedArray()[posarr[p]]);
                if(best != oldbest) {
                    bestpos = p;
                }


            }
            posarr[bestpos]++;
            result[i] = best;
        }

        return result;

    }

    static int bestOf(int a, int b) {
        if(a == -1) return b;
        // you'll have to write this yourself :)
        String as = a+"";
        String bs = b+"";
        if(as.compareTo(bs) < 0) return a;
        return b;
    }

    static int numKeys(int i) {
        if(i < 0) throw new IllegalArgumentException("I don't deal with negative numbers");
        if(i == 0) return 1;
        //return (i+"").length(); // lame method :}
        int len = 0;
        while(i > 0) {
            len++;
            i /= 10;
        }
        return len;
    }

    public static void main(String[] args) {

        int[] test = {1, 6, 31, 65, 143, 316, 93, 736};
        int[] res = radixSort(test);
        for(int i : res) System.out.println(i);
    }
}

One thing that looks strange:

  for (int p = 0; p < n; p++){
    while(queue[p].count() != 0) {
      q[p] = (queue[p].get());
    }
  }

Is p supposed to be the index in q, which ranges from 0 to n-1, or in queue, which ranges from 0 to 9? It is unlikely to be both ...

Another:

  for (int index = 0; index < n; index++){
    // trying to look at one of three digit to sort after.
    int v=1;
    int digit = (q[index]/v)%10;
    v*=10;

    queue[digit].put(q[index]);
  }

Why are you multiplying v by 10, only to overwrite it by v = 1 in the next iteration? Are you aware than v will always be one, and you will thus look at the same digit in every iteration?

Well I don't think I can help without almost posting the solution (just giving hints is more exhausting and I'm a bit tired, sorry), so I'll just contribute a nice little fuzz test so you can test your solution. How does that sound? :-)

Coming up with a good fuzztester is always a good idea if you're implementing some algorithm. While there's no 100% certainty if that runs with your implementation chances are it'll work (radix sort doesn't have any strange edge cases I'm aware of that only happen extremely rarely)

private static void fuzztest() throws Exception{
    Random rnd = new Random();
    int testcnt = 0;
    final int NR_TESTS = 10000;
    // Maximum size of array.
    final int MAX_DATA_LENGTH = 1000;
    // Maximum value allowed for each integer. 
    final int MAX_SIZE = Integer.MAX_VALUE; 

    while(testcnt < NR_TESTS){
     int len = rnd.nextInt(MAX_DATA_LENGTH) + 1;
     Integer[] array = new Integer[len];
     Integer[] radix = new Integer[len];

     for(int i = 0; i < len; i++){
      array[i] = rnd.nextInt(MAX_SIZE);
      radix[i] = new Integer(array[i]);
     }

     Arrays.sort(array);
     sort(radix);  // use your own sort function here.

     for(int i = 0; i < len; i++){
      if(array[i].compareTo(radix[i]) != 0){
       throw new Exception("Not sorted!");
      }
     }
     System.out.println(testcnt);
     testcnt++;
    }