title: Quicksort algorithm with duplicate keys
body: <p>I am trying to implement Quick Sort algorithm.  Following code works for unique elements but it doesn't working for arrays having duplicate  elements. Please tell me where I am doing wrong. Also when I change value of pivot to some other number other than 0 , program crashes. Here is the code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;cstdlib&gt;
  
  using namespace std;
  
  void swapme(int &amp;a, int &amp;b)
  {
      int temp = a;
      a = b;
      b = temp;
  }
  
  void quicksort(int *arr, int size)
  {    
      // these two variables will take care of position of comparison
      int lower = 0, upper = size - 1;  
      int pivot = 0;  // assigns pivot
      if (size &lt;= 1)
          return;
  
      while (lower &lt; upper)
      {
          while (arr[lower] &lt; arr[pivot])
          {
              ++lower;
          }
      }
  
      while (arr[upper] &gt; arr[pivot])
      {
          --upper;
      }
  
      if (upper &gt; lower)
      {
          swapme(arr[upper], arr[lower]);
          // upper--;
          // lower++;
      }
  
      quicksort(arr, lower);
      quicksort(&amp;arr[lower + 1], size - 1 - lower);
  }
  
  int main()
  {
      int arr[30];
  
      for(int j = 0; j &lt; 30; j++)
      {
          arr[j] = 1 + rand() % 5000;
      }
  
      for(int j = 0; j &lt; 30; j++)
      {
          cout &lt;&lt; arr[j] &lt;&lt; "\t";
      }
      cout &lt;&lt; endl;
  
      quicksort(arr, 30);
  
      for(int j = 0; j &lt; 30; j++)
      {
          cout &lt;&lt; arr[j] &lt;&lt; "\t";
      }
      cout &lt;&lt; endl;
  
      cin.get();
      cin.get();
  }
  </code></pre>
  
  <p><strong>Update:</strong> I have finally managed to make it work. Here is the fixed version:</p>
  
  <pre><code>void swapme(int &amp;a, int &amp;b )
  {
      int temp = a;
      a = b;
      b = temp;
  }
  
  void quicksort(int *arr, int size)
  {
      if (size &lt;= 1)
          return;
  
      // These two variables will take care of position of comparison.
      int lower = 0;
      int upper = size-1;  
  
      int pivot = arr[upper/2]; // assigns pivot
  
      while (lower &lt;= upper)
      {
          while (arr[lower] &lt; pivot)
              ++lower;
          while (arr[upper] &gt; pivot)
              --upper;
  
          if (upper &gt;= lower)
          {
              swapme(arr[upper],arr[lower]);
              if(arr[upper] == arr[lower])
              {
                  // Can either increment or decrement in case of duplicate entry
                  upper--; // lower++;
              }
          }
      }
  
      quicksort(arr, lower);
      quicksort( &amp;arr[lower+1], size-1-lower);
  }
  </code></pre>