title: Count the number of component wise comparisons in quicksort algorithm.
body: <p>I'm trying to count the number of comparisons my quicksort algorithm makes for an array size of 500. I know that the best case for quicksort with partition is nlogn-n+1. So for an array size of 500, the best case number of component wise comparisons would be about 3983. However, when I run my code, I'm getting 2400 comparisons or so, depending on the array the random function generates. Am I counting the number of component wise comparisons wrong? Please help. </p>
  
  <pre><code>#include &lt;iostream&gt;
      #include &lt;string&gt;
      #include &lt;stdlib.h&gt;
      using namespace std;
  
  
      int count_500 = 0;
  
      int partition(int *S,int l, int u);
      void swap(int &amp;val1, int &amp;val2);
      void Quicksort(int S[],int low, int hi);
      void exchange(int list[], int p, int q);
      int median_of_3(int list[], int p, int r);
      void Quicksort_M3(int S[], int low, int hi);
  
  
  
  
  
      int main()
      {
              int S1_500[500];
              int S2_500[500];
              int S3_500[500];
  
              int S1_200[200];
              int S2_200[200];
              int S3_200[200];
  
              int S1_8[8];
              int S2_8[8];
              int S3_8[8];
  
              srand ( time(NULL) );
  
  
  
              for(int i=0; i&lt;500; i++)
              {
                      S1_500[i] = rand()%1000;
                      S2_500[i] = rand()%1000;
                      S3_500[i] = rand()%1000;
              }
  
              for(int i=0; i&lt;200; i++)
              {
                      S1_200[i] = rand()%500;
                      S2_200[i] = rand()%500;
                      S3_200[i] = rand()%500;
              }
  
              for(int i=0; i&lt;8; i++)
              {
                      S1_8[i] = rand()%100;
                      S2_8[i] = rand()%100;
                      S3_8[i] = rand()%100;
              }
  
              Quicksort(S1_500,0,499);
              for(int i=0; i&lt;500; i++)
              {
                      cout &lt;&lt; S1_500[i] &lt;&lt; endl;
              }
  
              cout &lt;&lt; "Number of component wise comparisons is: " &lt;&lt; count_500 &lt;&lt; endl;
  
  
  
  
  
      }
  
  
      int partition(int *S,int l, int u)
      {
              int x = S[l];
              int j = l;
              for(int i=l+1; i&lt;=u; i++)
              {
                      if(S[i] &lt; x)
                      {       
                              count_500++; // Count the component wise comparison
                              j++;
                              swap(S[i],S[j]);
                      }
              }
              int p = j;
              swap(S[l],S[p]);
              return p;
      }
  
      void swap(int &amp;val1, int &amp;val2)
      {
              int temp = val1;
              val1 = val2;
              val2 = temp;
      }
  
      void Quicksort(int S[],int low, int hi)
      {
              if (low &lt; hi)
              {
                      int p = partition(S,low,hi);
                      Quicksort(S,low,p-1);
                      Quicksort(S,p+1,hi);
              }
      }
  </code></pre>