OutOfMemoryError in a quicksort implementation in Java
I'm trying to implement a Quicksort algorithm, I have read how to do it with pseudocode and since I'm learning Java ('cause I have already done quicksort some months ago in C++) I want to implmenet it to such language, but I get an stackoverflow or heap space problem whenever I try to run it, can you please check my code? :D
public static int[] quicksort(int arreglo[]){
int size=arreglo.length;
int pivote=arreglo[size/2];
int menor[] = new int[size+2]; //If I leave the +2 I get stack overflow
int mayor[] = new int[size+2]; //If I delete them I get heap space problems
int j=0,k=0;
if(size>2){
for(int i=0;i<size;i++){
if(arreglo[i]<=pivote){
menor[j]=arreglo[i];
j++;
}
else{
mayor[k]=arreglo[i];
k++;
}
}
if(menor.length>=1&&mayor.length>=1)
return concatena(Ordena.quicksort(menor),Ordena.quicksort(mayor),j,k);
else
if(menor.length>mayor.length)
return menor;
else
return mayor;
}
else
return arreglo;
}
public static int[] concatena(int menor[],int mayor[],int limite1,int limite2){
int completo[] = new int[limite1+limite2];
System.arraycopy(menor,0,completo,0,limite1);
System.arraycopy(mayor,0,completo,limite1,limite2);
return completo;
}
Thanks for all your comments and answers, I have made the suggested changes, I will paste the exact exception:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at Ordena.quicksort(Ordena.java:6) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) 开发者_运维百科 at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21)
And here's the modified code (I have translated my variables, sorry I haven't noticed):
public static int[] quicksort(int array[]){
int size=array.length;
int pivot=array[size/2];
int less[] = new int[size+2];
int greater[] = new int[size+2];
int j=0,k=0;
if(size>2){
for(int i=0;i<size;i++){
if(array[i]<=pivot){
less[j]=array[i];
j++;
}
else{
greater[k]=array[i];
k++;
}
}
less[j]=pivot;
if(j>=1&&j>=1)
return concatenate(Ordena.quicksort(less),Ordena.quicksort(greater),j,k);
else
if(j>k)
return less;
else
return greater;
}
else
return array;
}
public static int[] concatenate(int less[],int greater[],int limit1,int limit2){
int complete[] = new int[limit1+limit2];
System.arraycopy(less,0,complete,0,limit1);
System.arraycopy(greater,0,complete,limit1,limit2);
return complete;
}
The major problem stems from this line:
if(menor.length>=1&&mayor.length>=1)
which should be
if(j>=1&&k>=1)
Why? Well, the first statement is always true, and when all of the elements being partitioned are equal to or less than the pivot, all of them will be in mayor in the exact same order that they came in. quicksort is called again on the function which does the exact same partitioning and you get an infinite loop. Depending on how big you make the menor or mayor arrays, the program is erroring on a stack overflow or a memory error first.
Even if you change the above line, your sort won't work as you have it. Why? Well, there are several reasons. First, the line
if(menor.length>mayor.length)
should be
if(j>k)
However, that is just part of the problem. You won't be continuing to sort mayor or menor when they contain all of the elements input to the function. However, if you send them on to quicksort then you can still have an infinite loop. What I would recommend is separating the pivot from the rest of the array that is input to quicksort (swap it with the first element for instance) and partition the rest of the array. Then put the pivot in place between the partitioned mayor and menor arrays after those arrays have been quicksorted themselves.
Good luck.
精彩评论