title: Counting comparisons in quicksort
body: <p>I am trying to calculate number of comparisons for <code>quicksort</code>. For the worst case scenario, it shows n*n-1/2 comparisons. So for 8 inputs in the order 8 7 6 5 4 3 2 1, it should be 28 comparisons. However, in my program there are 30 comparisons. I tried to print comparisons and all were fine but the last comparison is repeated thrice. Anyone could find the fault with this code?</p>
  
  <pre><code>#include&lt;iostream.h&gt;
  #include&lt;conio.h&gt;
  int ar[10000];
  int pivot;
  int temp;
  int partition(int x, int y);
  void quicksort(int f, int l);
  int count = 0;
  int i;
  int index;
  void main() {
    clrscr();
    int i;
    for (i = 0; i &lt; 8; ++i) {
      cin &gt;&gt; ar[i];
    }
    quicksort(0, 7);
    cout &lt;&lt; "\nThe sum is  " &lt;&lt; sum;
    getch();
  }
  void quicksort(int f, int l) {
    if (f == l)
      return 0;
    if (f &lt; l) {
      pivot = partition(f, l);
      quicksort(f, pivot - 1);
      quicksort(pivot + 1, l);
    }
  }
  int partition(int f, int l) {
    index = ar[f];
    i = f + 1;
    for (int j = f + 1; j &lt;= l; ++j) {
      if (ar[j] &lt; index) {
        temp = ar[j];
        ar[j] = ar[i];
        ar[i] = temp;
        ++i;
      }
    }
    i = i - 1;
    temp = ar[f];
    ar[f] = ar[i];
    ar[i] = temp;
    return i;
  }
  </code></pre>