0

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);
dbank
  • 1,173
  • 1
  • 17
  • 29
Jihad Tamimi
  • 13
  • 3
  • 6
    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 Mar 24 '15 at 18:50
  • Why code your own quicksort when this wheel has already been invented? – Mike Nakis Mar 24 '15 at 18:53
  • @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 Mar 24 '15 at 18:58
  • 1
    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 Mar 24 '15 at 19:03

1 Answers1

2

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.

Community
  • 1
  • 1
juhist
  • 4,210
  • 16
  • 33
  • its a homework , but it was already copied ... the teacher doesn't care about the code he wants the chart only – Jihad Tamimi Mar 24 '15 at 19:01
  • Perhaps you should then report that the algorithm didn't work for these cases? And better yet, explain _why_ it didn't work. Read my edited answer and try to understand it. – juhist Mar 24 '15 at 19:03
  • 1
    And oh, I should mention that using already sorted arrays for benchmarking sorting algorithm will result in incorrect data. Garbage in, garbage out. So, please don't use already sorted arrays for your test case unless specifically instructed to do so by the teacher or by the problem statement. – juhist Mar 24 '15 at 19:04
  • thanks for the answer , and he ordered us to use a sorted data to show the difference between the balanced(best) case , unbalanced(worst) case and random(average) case , obviously. – Jihad Tamimi Mar 24 '15 at 19:06
  • Oh, then you did exactly what you should have done. Just report that it didn't work due to a stack overflow and _why_ it didn't work. – juhist Mar 24 '15 at 19:08