Marenthyu - 3 months ago 6x

Java Question

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
```

Source (Stackoverflow)

Comments