meallhour meallhour - 1 month ago 21
Java Question

QuickSort giving exception in thread "main" java.lang.StackOverflowError

I have written quick sort code as below. The sort takes middle number as pivot:

import java.util.Arrays;

public class QuickSort {

public static void main(String[] args) {

int[] numbers = {3, 6, 9, 1, 34};

int low = 0;

int high = numbers.length - 1;

quicksort(numbers, low, high);

}

static void quicksort(int[] arr, int low, int high) {

int i = low;
int j = high;

int middle = arr[(low + high) / 2];

while(i < j) {
while(arr[i] < middle ) {
i++;
}

while(arr[j] > middle) {
j--;
}

if( i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}


}

if(low < j) {
quicksort(arr, low, j);
}

if(i < high) {
quicksort(arr, i, high);
}

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

}

}


However, after running the code i am getting stackoverflow exception.
It says Exception in thread "main" java.lang.StackOverflowError

Exception in thread "main" java.lang.StackOverflowError
at QuickSort.quicksort(QuickSort.java:47)
at QuickSort.quicksort(QuickSort.java:47)
at QuickSort.quicksort(QuickSort.java:47)
at QuickSort.quicksort(QuickSort.java:47)
at QuickSort.quicksort(QuickSort.java:47)
at QuickSort.quicksort(QuickSort.java:47)
at QuickSort.quicksort(QuickSort.java:47)


Please help me find out what might be wrong in running the above code.

Answer

The value of i and j needs to be incremented and decremented respectively. Please see below the working code:

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {

        int[] numbers = {3, 9, 6, 1, 34};

        int low = 0;

        int high = numbers.length - 1;

        quicksort(numbers, low, high);  

    }

    static void quicksort(int[] arr, int low, int high) {

        int i = low;
        int j = high;

        int middle = arr[(low + high) / 2];

        while(i <= j) {      
            while(arr[i] < middle ) {
                i++;
            }

            while(arr[j] > middle) {
                j--;
            }

            if( i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                i++;
                j--;
            }


        }

        if(low < j) {
            quicksort(arr, low, j);         
        }

        if(i < high) {
            quicksort(arr, i, high);
        }

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

    }

}

Hope this helps!