title: Quick sort with pointers
body: <p>I need to code a quick sort algorithm in C as homework. This is the prototype I was given:</p>
  
  <pre><code>static inline
  int* choose_pivot(int *left, int *right) {
      /* FIX ME */
  }
  
  /*
   * partition(left, right, pivot): push value less than *pivot on the left
   * return the new pivot.
   */
   int* partition(int *left, int *right, int *pivot) {
       /* FIX ME */
   } 
  
   /*
   * quick_sort(left, right)
   */
   void quick_sort(int *left, int *right) {
       /* FIX ME */
   }
  </code></pre>
  
  <p>where <code>left</code> is the pointer to the first element of the array and <code>right</code>, the pointer to the last element (excluded). I wrote the following code:</p>
  
  <pre><code>static inline
  int* choose_pivot(int *left, int *right) {
      return &amp;left[(right - left)/2];
  }
  
  void swap(int *a, int *b) {
      int c = *a;
      *a = *b;
      *b = c;
  }  
  
  int* partition(int *left, int *right, int *pivot) {
      int *i, *q;
      q = right;
      i = left ;
      while ( q &gt; pivot ) {
          while ( pivot &lt; i )
              pivot++;
          while ( q &gt; i )
              q--;
          if ( *q &gt; *pivot ) {
             swap(pivot,q);
          }
      }
      swap(left, q);
      return q ;
  }
  
  void quick_sort(int *left, int *right) {
      if(left &gt;= right)
          return;
  
      int *pivot = partition(left, right, choose_pivot(left, right));
      quick_sort(left, pivot-1);
      quick_sort(pivot + 1, right);
  }
  </code></pre>
  
  <p>I am running 3 kind of tests: one on a sorted array, one on a reverse sorted one and,
  one on reverse sorted one. the first test works well, but the second and this ones fails. Basically meaning the functions doesn't work. I can't find any documentation on what I am supposed to do since all quick sort algorithm uses its length instead of a pointer on the last element and I couldn't adapt the ones I've found to my representation. What is going wrong here?</p>
  
  <p>EDIT:</p>
  
  <p>My new partition function now looks like this after the comments:</p>
  
  <pre><code>int* partition(int *left, int *right, int *pivot) {
      int *i, *q;
      q = right;
      i = left ;
      int p = *pivot;
  
      while ( q &gt; pivot ) {
          while ( p &lt; *i )
              pivot++;
          while ( *q &gt; *i )
              q--;
          if ( q &gt; pivot ) {
              swap(pivot,q);
          }
      }
  
      swap(left, q);
      return q ;
  }
  </code></pre>