java quicksort stack overflow

Question

i am still a beginner and i am trying to write a quick sort code

here is my code

package algo_quicksort;

public class Algo_quicksort {

    public static int partition(int[]A,int p,int r){
        int x=A[p];
        int i=p+1;
        int temp;
        for(int j=p+1;j<r;j++){
            if(A[j]<x){//if A[j] is bigger than the pivot do nothing 
                temp=A[j];
                A[j]=A[i];
                A[i]=temp;
                i++;
            }
        }
        temp=A[p];
        A[p]=A[i-1];
        A[i-1]=temp;
        return i-1;
    }

    public static void quickSort(int[]A,int starPos,int length){
        if(length==1){
            return;
        }
        else{
         if(startPos<length){
        int pivot= partition(A,0,length);
       quickSort(A,startPos,pivot+1);

        quickSort(A, pivot+2,length); 

        }
    }}


    public static void main(String[] args) {
        int a[]={6,5,4,3,2,1};
        System.out.println("A[] after quicksort is: ");

        quickSort(a,0, a.length);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }
    }
}

i get a stack over flow exception in the recursive calls

i do not see why and i would appreciate any help i get ^_^

I suggest you find the simplest case where this happens and use you debugger to step through the code to see what it is doing and why. — Peter Lawrey
– Peter Lawrey, Commented Aug 5, 2013 at 15:37

Nir Alfasi · Accepted Answer · 2013-08-05 16:05:03Z

1

There are many bugs in this program, here are a few that I found:

You don't use starPos in quickSort()
You don't use length (you use A.length) in quickSort()
The pivot "overlaying" issue that charles mentioned
In partition() you should switch places of the item that is right to the pivot and smaller with an item that is left to the pivot and is bigger - you don't do that.

and there's probably more. You can see an implementation I did for quicksort in Ruby (it's easy to migrate it to Java) and compare to your implementation until you get it right - it's trickier than most people think!

http://alfasin.com/playing-with-ruby/

edited Aug 5, 2013 at 16:05

answered Aug 5, 2013 at 15:47

Nir Alfasi

53.6k11 gold badges94 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

charles_ma · Accepted Answer · 2013-08-05 15:43:54Z

1

I didn't read it carefully but in

quickSort(A,0,pivot+1);
quickSort(A, pivot,A.length-pivot);

you definitely over count the element A[pivot] in two branches of your recursive method

answered Aug 5, 2013 at 15:43

charles_ma

7867 silver badges10 bronze badges

Collectives™ on Stack Overflow

java quicksort stack overflow

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related