Stackoverflow exception caused by recursive call of partitionStep in QuickSort

Question

I try to implement quicksort algorithm for int[]. I coded the partition step correctly but then I wanted to call partition step method recursively to get the array sorted, unfortunately I pass wrong indexes to the recursive call and I get StackOverflow exception.

I based it on: https://www.youtube.com/watch?v=y_G9BkAm6B8

public class Quicksort {

    public static void partition(int[] t, int i, int j) {

        int start = i, end = j;
        int pivot = t[(i + j) / 2]; // select the pivot as the middle value
        System.out.println("pivot: " + pivot);
        int temp;
        while (i < j) {
            while (t[i] < pivot) { // looking for value greater or equal to the
                                    // pivot
                i++;
            }
            while (t[j] > pivot) { // looking for value lower or equal to the
                                    // pivot
                j--;
            }
            System.out.println("i = " + i + " j = " + j + " swaps " + t[i] + " with " + t[j]);
            temp = t[i]; // swap
            t[i] = t[j];
            t[j] = temp;
            i++; // move to the next element
            j--; // move to the prev element
            display(t);
        }
        // I CALL THEM WRONG
        partition(t, start, j); // partition for the left part of the array
        partition(t, i, end); // partiion for the right part of the array
    }

    public static void display(int[] t) {
        for (int el : t)
            System.out.print(el + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] t = { 6, 4, 1, 32, 5, 7, 8, 6, 9, 1 };
        display(t);
        partition(t, 0, t.length - 1);
    }
}

Answer 1

The fundamental problem is that your recursion has no exit condition. You don't have a single return statement in your partition method. When your while loop exits, it will just make additional call into the partition method again. But there's nothing in the code to say, "stop making recursive calls into partition". Hence, the stack overflow.

I think you want to at least say this at the top of the partition function. This should clear up the stack overflow.

public static void partition(int[] t, int i, int j) {
    if (i >= j)  {
        return;
    }

Also I'm not sure, but shouldn't this line:

partition(t, j, end); //partiion for the right part of the array

Really be this:

partition(t, i+1, end); //partiion for the right part of the array

Answer 2

You are missing the if statement to check whether i is less than or equal to j after the while...

public class QuickSort {

public static void display(int[] arr){
    for(int i = 0; i < arr.length; i++) {
        System.out.println( arr[i] );

    }
}

public static void main( String[] args ) {
    int[] data = new int[]{ 5, 10, 1, 9, 4, 8, 3, 6, 2, 6,7 };
    System.out.println("Unsorted array : " );
    display( data );
    quickSort( data, 0, data.length - 1 );
    System.out.println( "Sorted array: " );
    display( data );
}

public static void quickSort( int[] arr, int left, int right ) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[( left + right ) / 2];
    while( i <= j ) {
        while( arr[i] < pivot ) {
            i++;
        }
        while( arr[j] > pivot ) {
            j--;
        }
        // You forgot to test here...
        if( i <= j ) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    if( left < j ) {
        quickSort( arr, left, j );
    }
    if( i < right ) {
        quickSort( arr, i, right );
    }
}

}

Answer 3

Also if you are doing deep recursive calls you may want to look into enlarging the stack size using the -Xss argument. You can find a full answer here: How to increase the Java stack size?

I know that your code is problematic and not the actual size of the stack but this may prove useful once you've fixed the code.