Custom QuickSort not working in java

Question

I have implemented QuickSort, but for some weird reason, my code is giving StackOverflow exception. I have been banging my head to understand why my code is breaking any ideas why my code is broken? is there any other way to optimize this? recursion is causing my stack to overflow; but can't place where this is happening!

   import java.io.*;
   import java.util.*;
   import java.text.*;
   import java.math.*;
   import java.util.regex.*;

public class Solution {

    static void quickSort(int[] arr,int low,int high) {
        // Complete this function
        int p =partition(arr,low,high);
         System.out.println("partiion at p[]"+p); 
        if(low<p){

            System.out.println("starging quickSort at low[]"+low+" hgh["+(p-1)); 
            quickSort(arr,low,p-1);    
        }

        if(p<high){
            System.out.println("starging quickSort at low[]"+p+1+" hgh["+high); 
            quickSort(arr,p+1,high);    
        }


    }
    static void swap(int []a,int x,int y){
        int tmp = a[y];
        a[y]=a[x];
        a[x]=tmp;
    }

    static int partition(int[] arr,int low,int high){
        int pivot = arr [low+ (high-low)/2];
        int left  = low;
        int right = high;
        System.out.println("pivot["+pivot+"] left ["+left+"]right["+right+"]");


        while(left<= right)
        {

            while(arr[left] < pivot){
                left++;
            }
            System.out.println("**..done now left ["+left+"]");


            while(arr[right] >pivot){
                right--;
            }

            System.out.println("##..done now right ["+right+"]");

            if(left <=right){
                swap(arr,left,right);
                right--;
                left++;
            }

                        System.out.println("#swapping");


            for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i != arr.length - 1 ? " " : ""));
        }

            System.out.println("done#swapping");
        }            

        return left;
    }
    static int[] quickSort(int[] arr) {
        quickSort(arr,0,arr.length-1);
        return arr;

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int arr_i = 0; arr_i < n; arr_i++){
            arr[arr_i] = in.nextInt();
        }
        System.out.println("ubsoted ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i != arr.length - 1 ? " " : ""));
        }
        System.out.println("");

        int[] result = quickSort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + (i != result.length - 1 ? " " : ""));
        }
        System.out.println("");


        in.close();
    }
}

A `StackOverflowError` is usually an indication of a [infinite loop](https://en.wikipedia.org/wiki/Infinite_loop) of recursive function calls. See also "[What is a StackOverflowError?](https://stackoverflow.com/q/214741/1347968)". — siegi, Apr 27 '18 at 20:56

score 1 · Answer 1 · answered Apr 27 '18 at 20:11

You have no return statement specified, thats why the stack overflows when quicksort is called recursively.

So ,add a return condtion like this,in quick sort method as first statement.

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

     if (high <=low) {
         return;
     }

Custom QuickSort not working in java

1 Answers1