QuickSort java.lang.StackOverflowError

Question

I am trying to calculate the execution time of quicksort algorithm in three cases "Mid pivot, first pivot, random pivot" of an array was already sorted.

The mid pivot and random works fine with any size, but the first pivot case gives stackoverflow if the size was greater than 25000.

Heres the code:

static void q_sort( int left, int right)
{

int pivot;
int l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = array[left];
  while (left < right)
  {
    while ((array[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      array[left] = array[right];
      left++;
    }
    while ((array[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      array[right] = array[left];
      right--;
    }
  }
  array[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(left,(int) pivot-1);
  if (right > pivot)
    q_sort( (int)pivot+1, right);
}

and heres the calling code:

double startTime1 = System.currentTimeMillis();
q_sort(0,size -1);
double stopTime1 = System.currentTimeMillis();
double elapsedTime1 = stopTime1 - startTime1;      
System.out.println(elapsedTime1);

Your code would be a lot easier to understand if you didn't keep reusing existing variables to mean different things - currently pivot means the pivot value half the time, and an index for the rest of the time. Very confusing! — Jon Skeet
Why code your own quicksort when this wheel has already been invented? — Mike Nakis
@JonSkeet its not my code i copied from here i am just testing the executing time for my teacher ... So any help guys? — Jihad Tamimi
If you can't change the code then there is no point in us debugging it. If you're accurately measuring the execution time then you're done. It's not your fault if the thing blows up. Just catch the exception, recover, and report the results. — candied_orange

juhist juhist · Accepted Answer · 2015-03-24T18:58:24

You didn't tell how the array was generated, but I suspect it was already sorted.

The problem is the following: if you quicksort an already sorted array, the first pivot causes the following recursion: 0..24999, 1..24999, 2..24999, 3..24999, 4..24999 which takes a lot of stack space and results in a stack overflow. This is because the array is 0..24999 and the pivot is 0, and the second partition then will become 1..24999.

You should eliminate one of the tail calls. Which tail call to eliminate depends on which partition is smaller. You want the recursion to process as little data as possible. One of the recursions is simply replaced by a loop. This tail recursion elimination has already been explained at Quicksort and tail recursive optimization

Anyway, I recommend using an existing quicksort algorithm instead of coding it yourself unless this is a homework question.

QuickSort java.lang.StackOverflowError

1 Answers