Stack overflow error with Quicksort and median implementation

Question

First of all I'm just going to state that this is a homework question which I have made an extensive amount of attempts on.

I've been asked to modify quicksort in Java to set the pivot as the psuedo median of 9 values in the array using the formula i * (n-1) /8

I wrote a computeMedian method which accepts 3 integers, determines the highest, and then returns that value.

The code:

public static int computeMedian(int x, int y, int z)
    {
        if((x >= y && x <= z) || (x >= z && x <= y)) {return x;}
        else if((y >= x && y <= z) || (y >= z && y <= x)) {return y;}
        else if((z >= x && z <= y) || (z >= y && z <= x)) {return z;}
        else { return 0; }
    }

I then used it in my findPivot method which takes the current array, from, to values and uses them to construct a pivot

Here is that code:

public static int findPivot(int[] a, int from, int to)
    {
        if(a.length <= 7)
        {
            return a[(to)/2];
        }
        else if(a.length > 7 && a.length <= 40)
        {
            return computeMedian(a[from], a[(to)/2] , a[to]);
        }
        else
        {
            int x = computeMedian(a[0 * (to) / 8], a[1 * (to) / 8], a[2 * (to) / 8]);
            int y = computeMedian(a[3 * (to) / 8], a[4 * (to) / 8], a[5 * (to) / 8]);
            int z = computeMedian(a[6 * (to) / 8], a[7 * (to) / 8], a[8 * (to) / 8]);
            return computeMedian(x,y,z);
        }
    }

This method is working fine for sorting any array less than or equal to size 40, but as soon as it gets larger than 40 I recieve a stack overflow error leading back to my computeMedian method in the else {} portion. I will note that return computeMedian(a[from], a[(to)/2] , a[to]); works in the > 40 portion if I put it there, but that is only the median of 3 values as opposed to the median of the median of 3 sets.

Currently this is how I have findPivot plugged into the quicksort partitioning method:

private static int modPartition(int[] a, int from, int to)
    {
        int pivot = findPivot(a, from, to);
        int i = from - 1;
        int j = to + 1;
        while(i < j)
        {
            i++; while (a[i] < pivot) { i++; }
            j--; while (a[j] > pivot) { j--; }
            if (i < j) { swap(a, i, j); }
        }
        return j;
    }

I'm pretty much stumped on why my computeMedian method fails to work on larger datasets. I've tried placing the i * (n-1) / 8 values in an array via a for loop, sorting them and returning the value in the middle as well as placing the values in an array p and calling computeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etc and I get the same stack overflow issue but it tends to move around to different portions of my code and leading me in circles.

I can post any more snippets if anyone needs but I think my issue is right here probably.

Thanks for the help. I'm still learning and I think getting a grip on this would totally help me problem solve in the future on my own.

Here are the problem lines from the stack trace: Line 16: int p = modPartition(a, from, to); Line 18 modSort(a, p+1, to); Line 23 int pivot = findPivot(a, from, to);

Heres my entire modSort method also:

public static void modSort(int[]a, int from, int to)
    {
        if(from >= to) { return; }
        int p = modPartition(a, from, to);
        modSort(a, from, p);
        modSort(a, p+1, to);
    }

Answer 1

Reproduced and corrected

Code added to reproduce the error ...

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

public static void main(String[] args) {
    // Generate a sample
//      ArrayList<Integer> list = new ArrayList<>(64);
//      for (int i = 0; i < 64; i++) list.add(i);
//      Collections.shuffle(list);
//      System.out.println(list);
    int[] arr = {40, 9, 2, 62, 8, 42, 46, 23, 61, 45, 63, 48, 43, 36, 33, 32, 1, 55, 7, 17, 16, 25, 5, 26, 22, 11, 56, 38, 60, 31, 58, 29, 51, 34, 24, 54, 4, 3, 30, 20, 57, 18, 50, 44, 41, 12, 59, 6, 53, 39, 37, 35, 28, 13, 14, 15, 0, 19, 49, 52, 21, 27, 47, 10};

    modSort(arr, 0, arr.length-1);

    System.out.println(Arrays.toString(arr));
}

Debugging. Setting breakpoint for StackOverFlowError (as suggested in comments) didn't work. So I go for a regular breakpoint at line (start of modSort).

For this sample data starts doing infinite recursion over modSort with from=3;to=5. For that range the pivot p=2, which seems abnormal.

I blame findPivot(a,from,to) method. Looks good for finding a pivot for the whole a, but not for a range. Trying this correction:

public static int findPivot(int[] a, int from, int to) {
    final int rangeLength = to - from + 1;
    if(rangeLength <= 7) {
        return a[(from + to)/2];
    } else if(rangeLength  <= 40) { // why test "a.length > 7" ?
        return computeMedian(a[from], a[(from + to)/2] , a[to]);
    } else {
        final int rangeLength_8 = (to - from) / 8;
        int x = computeMedian(a[from], a[from + rangeLength_8], a[from + 2 * rangeLength_8]);
        int y = computeMedian(a[from + 3 * rangeLength_8], a[from + 4 * rangeLength_8], a[from + 5 * rangeLength_8]);
        int z = computeMedian(a[from + 6 * rangeLength_8], a[from + 7 * rangeLength_8], a[to]);
        return computeMedian(x,y,z);
    }
}

Then it works fine for my example. I stop it at this point (have to get some sleep).

I think you should try to get familiar with the debugger. I think it should had been easier for you to figure it out.

Answer 2

Now that you've actually included the code and the error message for the stack overflow issue, we can help you out.

From your stack trace, we can see that the infinite recursion is likely the second call to modSort, because line 18 is repeated.

Since the only difference between that call and the incoming parameters is the 2nd parameter, I'd bet money on p being less than from.

Best way to confirm that is in insert a good old-fashioned print statement.

public static void modSort(int[]a, int from, int to)
{
    if(from >= to) { return; }
    int p = modPartition(a, from, to);
    System.out.println("from=" + from + ", to=" + to + ", p=" + p);
    modSort(a, from, p);
    modSort(a, p+1, to);
}

The resulting output should show a very clear pattern of what's wrong.