CODEWITHSUNDEEP
javasortingdata-structuresquicksort
Porkko M
Porkko M

Reputation: 307

Quicksort Java code going to infinite loop

when i try to run the below quick sort code,its going to infinite loop.the last iteration is going to infinite loop.

class QuickSort {
    public static void main(String[] args) {
        int arr[] = {10, 7, 8, 9, 1, 5,2};
        QuickSort ob = new QuickSort();
        ob.sort(arr, 0,arr.length-1);
        for(int s:arr){
            System.out.print(" "+s);
        }
    }
    int partition(int[] arr,int l,int h){
        int piv = arr[h];
        int i=l-1;
        for(int j=l;j<=h-1;j++){
            if(arr[j] <= piv){
                i++;
                int temp = arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        int tp = arr[i+1];
        arr[i+1]=arr[h];
        arr[h]=tp;
        return i+1;
    }

    void sort(int[] arr,int l,int h){
        while(l<h){
            int p = partition(arr, l, h);
            sort(arr, l, p-1);
            sort(arr, p+1, h);
        }

    }
}

Kindly help,where it goes wrong.

Upvotes: 0

Views: 540

Answers (3)

nits.kk
nits.kk

Reputation: 5316

You have used while in the sort method. This results in infinite recursive calls which ultimately will cause StackOverFlowException. As suggested in the comments, these are the common mistakes and you can easily find them by debugging (or simple dry run for simple algorithms).

You just need two recursive calls form each invocation of the method sort which satisfies the condition (l < h ) For this you need a if condition insteadof while loop as below.

void sort(int[] arr,int l,int h){
    if(l<h){
        int p = partition(arr, l, h);
        sort(arr, l, p-1);
        sort(arr, p+1, h);
    }
 }

Upvotes: 1

Kaushal28
Kaushal28

Reputation: 5557

Instead of while loop, use if condition, as following. 

if(l<h){
        int p = partition(arr, l, h);
        sort(arr, l, p-1);
        sort(arr, p+1, h);
    }

There is no need to call sort recursively in an infinite while loop. Loop is infinite because l and r will never be changed in the algo.

Hope this help :)

Upvotes: 5

YounesM
YounesM

Reputation: 2317

l and h in sort() never change, so you'll always have l < h == true

Upvotes: 0

Related Questions