Marenthyu Marenthyu - 4 months ago 21
Java Question

Simple QuickSort Algorithm giving Stack Overflow Error?

My friend has a small problem and I'm at the end of my knowledge. He wrote a Simple (he got it in school) QuickSort Algorithm And it produces a StackOverflow Error. I know it means it calls itself recursive too many times somewhere, but I can't get the logical Error - please help me!

Here is the code (I'm leaving out some code as that is only to show it in 2 text areas):

int array [] = new int [10];
...
public static void quicksort (int array[],int l,int r){
int i = l;
int j = r;
int mitte = array [(l+r)/2];

while (i<j) {
while (array[i]<mitte) {
i++;
} // end of if
while (mitte<array[i]) {
j--;
} // end of if
if (i<=j) {
int merke =array[i];
array[i] = array [j];
array [j] = merke ;
i++;
j--;
} // end of if
if (i<j) {
quicksort(array,l,j);
} // end of if
if (l<r) {
quicksort(array,l,r);
} // end of if
} // end of while
}


It is called like this:

quicksort(array,0,9);


But, if We call it and the 2 numbers are the same, it gives no Overflow.

If more code is needed, here is the full Code on pastebin: http://pastebin.com/cwvbwXEu

Answer

First, you have an infinite loop here:

while  (mitte<array[i]) {
    j--;
  } // end of if

It needs to be array[j]

Secondly (and leading to the infinite recursion), in the second call to quicksort

if (l<r) {
  quicksort(array,l,r);
} // end of if

In recursion, you always need to shorten the range that you call yourself with, or else it'll be infinite. I haven't worked out exactly what you're doing, but I think you mean:

if (i<r) {
   quicksort(array,i,r);
 } // end of if