StackOverflowError in quick sort

Question

package arrays;

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

public class QuickSort {

    public static void main(String[] args){
        int[] arr = {7,2,4,8,1,6};
        int[] result = quick(arr,0, arr.length-1);
        for(int i=0; i< result.length; i++) {
            System.out.println(result[i]);
        }
    }

    private static int[] quick(int[] arr, int startIndex, int endIndex){
        if(startIndex<endIndex){
            int q= partition(arr,startIndex,endIndex);
            quick(arr, startIndex,q-1);
            quick(arr,q+1, endIndex);
        }
      return arr;
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
       int pivot = arr[endIndex];
       int i = startIndex-1;
       for(int j=startIndex; j<+arr.length;j++){
           if(arr[j]<=pivot){
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
           }
       }
       List<int[]> list = Arrays.asList(arr);
       return list.indexOf(pivot);
    }
}

I am getting StackOverFlowError for above code. I have dry run the code and it looks good to me. Can please some one help me to understand what's the issue?

Answer 1

First, you have a few small syntax mistakes:

1. For loop in partition: There's an extra + that redundant and the loop should go up to endIndex. Should be

for(int j = startIndex; j < endIndex; j++) {

2. if(arr[j]<=pivot){ => Should be if(arr[j] < pivot) { (Since you are looking for a number strictly smaller than the pivot, though your example should work without this change as well.

3. Lastly, your parition always returns -1, because you are calling indexOf` on a singleton list, which never includes the pivot. The correct way to get it would be:

int temp = arr[endIndex];
arr[endIndex] = arr[i + 1];
arr[i + 1] = temp;
return i + 1;

The full revised code:

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

public class QuickSort {

    public static void main(String[] args){
        int[] arr = {7,2,4,8,1,6};
        int[] result = quick(arr,0, arr.length-1);
        for(int i=0; i< result.length; i++) {
            System.out.println(result[i]);
        }
    }

    private static int[] quick(int[] arr, int startIndex, int endIndex){
        if(startIndex<endIndex){
            int q= partition(arr,startIndex,endIndex);
            quick(arr, startIndex,q-1);
            quick(arr,q+1, endIndex);
        }
      return arr;
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
       int pivot = arr[endIndex];
       int i = startIndex-1;
       for(int j=startIndex; j<endIndex;j++){
           if(arr[j]<=pivot){
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
           }
       }
       int temp = arr[endIndex];
       arr[endIndex] = arr[i + 1];
       arr[i + 1] = temp;
       return i + 1;
    }
}

You can check the pseudocode implementation here: https://www.geeksforgeeks.org/quick-sort/