[Shane Hudson]

Hi,

I had a conversation with a recruiter from Google the other day and he told me that before I apply (in October) for an internship I should make sure I am comfortable with algorithmsa and data structures. Since we don't learn those until next year I thought I should start now.

No matter what I do I keep getting out of bounds exceptions and cannot seem to pinpoint the problem.

My code is:

import java.util.Arrays;
import java.util.List;
import java.util.Random;


public class QuickSort {
    
    private Random rand;
    private int[] numbers;
    
    public QuickSort(int[] list)
    {
        rand = new Random();
        numbers = list;
    }

    public int[] getNumbers()
    {
        return numbers;
    }
    
    public void sort()
    {
        partition(0, numbers.length - 1);
    }
    
    private void partition(int left, int right)
    {
        System.out.print(Arrays.toString(numbers));
        int pivot = numbers[rand.nextInt() % numbers.length];
        int i = left;
        int j = right;
        while (i <= j)
        {
            while (numbers[i] < pivot)
            {
                i++;
            }
            while (numbers[j] > pivot)
            {
                j--;
            }

            if (i <= j)
            {
                swap(i,j);
                i++;
                j--;
            }
        }
        partition(j, left);
        partition(right, i);
    }

    private void swap(int i, int j) {
        int left = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = left
    }
}

I started off by using a book, then a tutorial on here... so the code is probably fairly familiar.

Any ideas what I am doing wrong?

Thanks,

Shane

[Dogstopper]

I'll tell you. Your error was NOT easy to find. I had to use my debugger and everything.

Your problem is with THIS statement:

        int pivotIndex = rand.nextInt() % numbers.length;
        int pivot = numbers[pivotIndex];

What you may not not know is that by default, randInt() returns a value between Integer.MIN_VALUE and Integer.MAX_VALUE, which includes negative numbers. Therefore, the modulus operator is returning a negative value. To fix you problem, you simply need to absolute value your range:

        int pivotIndex = Math.abs(rand.nextInt() % numbers.length);
        int pivot = numbers[pivotIndex];

Happy coding!

[blackcompe]

int pivot = numbers[rand.nextInt() % numbers.length];

The nextInt you're using can generate negative numbers. Use nextInt(numbers.length).

[Shane Hudson]

Neither solutions seem to have fixed it completely, but hopefully it brings me closer to it working! Thanks, I didn't even think about negative numbers haha.

[blackcompe]

Here's a working sort if you want a reference.

[Dogstopper]

I don't know what's going on totally. You should use your debugger and monitor the left and right variables. they're doing some pretty funky stuff. I suspect you need to reevaluate your loops. Instead of using loops, think this one through totally with recursion.

[Shane Hudson]

Well I managed to get one of the second years to go through it with me on IRC at about 2am haha... here is the fixed code for anybody in a similar situation.

import java.util.Random;


public class QuickSort implements Algorithm {

    private Random rand;
    private int[] numbers;

    public QuickSort(int[] list)
    {
        rand = new Random();
        numbers = list;
    }

    public int[] getNumbers()
    {
        return numbers;
    }

    public void sort()
    {
        partition(0, numbers.length-1);
    }

    private void partition(int left, int right)
    {
        int pivotIndex = Math.abs(rand.nextInt() % numbers.length);
        int pivot = numbers[pivotIndex];
        int i = left;
        int j = right;
        while (i <= j)
        {
            while (numbers[i] < pivot)
            {
                i++;
            }
            while (numbers[j] > pivot)
            {
                j--;
            }

            if (i <= j)
            {
                swap(numbers,i,j);
                i++;
                j--;
            }
        }

        if(j > left)
            partition(left,j);

        if(i < right)
            partition(i, right);

    }

    private void swap(int[] list, int i, int j) {
        int left = list[i];
        list[i] = list[j];
        list[j] = left;
    }
}

I am going to create a viewer/tester and go through all the algorithms that I can find, then github it.

EDIT:

Using the random pivot meant that the time it takes varies a lot. By changing int pivotIndex = Math.abs(rand.nextInt() % numbers.length); to int pivotIndex = (left + right) / 2; on average I seem to be saving about 50000 nanoseconds.

This post has been edited by Shane Hudson: 17 March 2012 - 05:53 AM