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 ^_^
There are many bugs in this program, here are a few that I found:
starPos
in quickSort()
length
(you use A.length
) in quickSort()
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!