Simple QuickSort Algorithm giving Stack Overflow Error?

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

mackworth · Accepted Answer · 2014-01-27 18:38:26Z

1

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

answered Jan 27, 2014 at 18:38

mackworth

5,9532 gold badges32 silver badges50 bronze badges

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

2 Comments

Marenthyu Over a year ago

It seems like it was a simple copying from board mistake by my friend. Thanks man.

mackworth Over a year ago

Note also that the recursion shouldn't be inside the while loop. Quicksort is (1) separate the array into two groups, one all below your "pivot" middle number and one all above, then (2) sort each groups with a single call to quicksort on each.

Mark Peters · Accepted Answer · 2014-01-27 18:30:28Z

1

This call:

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

recursively calls quicksort with the same arguments that were passed in, rather than calling with a smaller subproblem to solve. It will therefore infinitely recurse.

answered Jan 27, 2014 at 18:30

Mark Peters

81.3k17 gold badges163 silver badges196 bronze badges

Comments

user2535749 · Accepted Answer · 2014-01-27 18:31:33Z

1

if (l<r) 
quicksort(array,l,r);

Isnt l always less than r? this will cause an infinite recursion which is why you dont get an overflow if both values are the same.

answered Jan 27, 2014 at 18:31

user2535749

354 bronze badges

1 Comment

Marenthyu Over a year ago

doh of course! Sorry for my dumbness XD - thanks for the quick help!

Collectives™ on Stack Overflow

Simple QuickSort Algorithm giving Stack Overflow Error?

3 Answers 3

2 Comments

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Linked

Related