title: Why does this Quicksort work?
body: <p>I find this Quicksort partitioning approach confusing and wrong, yet it seems to work. I am referring to <a href="http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/quickSort.htm" rel="nofollow noreferrer">this pseudocode</a>. <strong>Note</strong>: they also have a C implementation at the end of the article, but it's very different from their pseudocode, so I don't care about that.</p>
  
  <p>I have also written it in C like this, trying to stay true to the pseudocode as much as possible, even if that means doing some weird C stuff:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  int partition(int a[], int p, int r)
  {
      int x = a[p];
  
      int i = p - 1;
      int j = r + 1;
  
      while (1)
      {
          do
              j = j - 1;
          while (!(a[j] &lt;= x));
  
          do
               i = i + 1;
          while (!(a[i] &gt;= x));
  
          if (i &lt; j)
          {
              int t = a[i];
              a[i] = a[j];
              a[j] = t;
          }
          else
          {
              for (i = 1; i &lt;= a[0]; ++i)
                  printf("%d ", a[i]);
              printf("- %d\n", j);
  
              return j;
          }
      }
  }
  
  
  int main()
  {
      int a[100] = //{8, 6,10,13,15,8,3,2,12};
                  {7, 7, 6, 2, 3, 8, 4, 1};
  
      partition(a, 1, a[0]);
      return 0;
  }
  </code></pre>
  
  <p>If you run this, you'll get the following output:</p>
  
  <blockquote>
    <p>1 6 2 3 4 8 7 - 5</p>
  </blockquote>
  
  <p>However, this is wrong, isn't it? Clearly <code>a[5]</code> does not have all the values before it lower than it, since <code>a[2] = 6 &gt; a[5] = 4</code>. Not to mention that <code>7</code> is supposed to be the pivot (the initial <code>a[p]</code>) and yet its position is both incorrect and lost.</p>
  
  <p>The following partition algorithm is taken from <a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow noreferrer">wikipedia</a>:</p>
  
  <pre><code>int partition2(int a[], int p, int r)
  {
      int x = a[r];
      int store = p;
  
      for (int i = p; i &lt; r; ++i)
      {
          if (a[i] &lt;= x)
          {
              int t = a[i];
              a[i] = a[store];
              a[store] = t;
  
              ++store;
          }
      }
  
      int t = a[r];
      a[r] = a[store];
      a[store] = t;
  
      for (int i = 1; i &lt;= a[0]; ++i)
          printf("%d ", a[i]);
      printf("- %d\n", store);
  
      return store;
  }
  </code></pre>
  
  <p>And produces this output:</p>
  
  <blockquote>
    <p>1 6 2 3 8 4 7 - 1</p>
  </blockquote>
  
  <p>Which is a correct result in my opinion: the pivot (<code>a[r] = a[7]</code>) has reached its final position.</p>
  
  <p>However, if I use the initial partitioning function in the following algorithm:</p>
  
  <pre><code>void Quicksort(int a[], int p, int r)
  {
      if (p &lt; r)
      {
          int q = partition(a, p, r); // initial partitioning function
  
          Quicksort(a, p, q);
          Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r.
      }
  }
  </code></pre>
  
  <p>... it seems to be a correct sorting algorithm. I tested it out on a lot of random inputs, including all 0-1 arrays of length 20. </p>
  
  <p>I have also tried using this partition function for a selection algorithm, in which it failed to produce correct results. It seems to work and it's even very fast as part of the quicksort algorithm however.</p>
  
  <p>So my questions are:  </p>
  
  <ol>
  <li>Can anyone post an example on which the algorithm DOESN'T work?  </li>
  <li>If not, why does it work, since the partitioning part seems to be wrong? Is this another partitioning approach that I don't know about?</li>
  </ol>