RadixSort algorithm run time

Question

So I have an assignment where I have to run different sorting algorithms on large numbers of randomly generated lists. Then, I have to submit a report comparing running times of the various algorithms. I've written the code of 3 sorting algorithms so far: quicksort, mergesort, and heapsort. I only have radix-sort left. Below is the code. This code is throwing me an ArrayIndexOutOfBoundsException on this line:

b[--bucket[(a[i] / exp) % 10]] = a[i];

but I can't quite figure out how to alter the code to make it correct.

public class RadixSort {

    public static void main(String[] args) {
        Random generator = new Random( System.currentTimeMillis() );
        Scanner scan = new Scanner(System.in);
        int size = scan.nextInt();
        int[] x = new int[size];

        long start = System.currentTimeMillis();

        for (int i = 0; i < size; i++)
            x[i] = getRandomNumberInRange(0, 100);

        radixSort(x);
        System.out.println(Arrays.toString(x));
        long runtime = System.currentTimeMillis() - start;
        System.out.println("Runtime: " + runtime);
    }    

    private static int getRandomNumberInRange(int min, int max) {
        if (min >= max)
            throw new IllegalArgumentException("max must be greater than min");

        return (int)(Math.random() * ((max - min) + 1)) + min;
    }

    public static void radixSort( int[] a) {
        int i, m = a[0], exp = 1, n = a.length;
        int[] b = new int[10];

        for (i = 1; i < n; i++)
            if (a[i] > m)
                m = a[i];

        while (m / exp > 0) {
            int[] bucket = new int[10];

            for (i = 0; i < n; i++)
                bucket[(a[i] / exp) % 10]++;
            for (i = 1; i < 10; i++)
                bucket[i] += bucket[i - 1];
            for (i = n - 1; i >= 0; i--)
                b[--bucket[(a[i] / exp) % 10]] = a[i];
            for (i = 0; i < n; i++)
                a[i] = b[i];
            exp *= 10;        
        }
    }    
}

That's not quite how radix sort works. Each bucket should hold an array of integers which are then regrouped in the main array for every digit. — The Javatar
– The Javatar, Commented Oct 2, 2016 at 15:20
I don't want to give the entire solution so you can learn better. But this is the hint: your buckets should be declared as ArrayList<int>[10] buckets; And in buckets[digit] you have to place numbers which divided by exp yield that last digit. — The Javatar
– The Javatar, Commented Oct 2, 2016 at 15:22
You can also keep your solution but you would have to give b array a size equal to a.length — The Javatar
– The Javatar, Commented Oct 2, 2016 at 15:26

Nikolas · Accepted Answer · 2016-10-02 15:23:04Z

1

It happens because you have explicitly defined the fixed size of int[] b array:

int[] b = new int[10];

That's the reason it overflows in case the input is bigger than 10.

Change it to the variable length of the array from a parameter.

int[] b = new int[a.length];

Moreover I reccomend you to fix the getting of input for numbers only in the interval (0; n>.

answered Oct 2, 2016 at 15:23

Nikolas

45k19 gold badges132 silver badges201 bronze badges

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

Collectives™ on Stack Overflow

RadixSort algorithm run time

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related