title: implementation of quick sort, almost working but not
body: <p>Tried implementing the quick sort algorithm with this piece of code <a href="http://ideone.com/9wUcaF" rel="nofollow noreferrer">here</a></p>
  
  <p>The code is almost working except one element in the array is not being sorted, I think it must have to do something with the <code>i,j</code> used in the <code>partition</code> function, not sure..</p>
  
  <p>Am I implementing it correct?</p>
  
  <p>These are the relevant functions :</p>
  
  <pre><code>int partition(int a[], int start, int end){
    int i,j,pivot,temp;
  
    pivot = a[end]; //select last elem as the pivot
    i = start;   // point i and j to before/after start end of the arr
    j= end-1;
  
    while(true){
      //reduce j until we reach an elem that is less than pivot
      if(a[j] &gt;= pivot){ j= j-1; }    
      //increase i until we reach an elem that is more than pivot
      if(a[i] &lt;= pivot){ i = i+1; }  
  
  
      if(i&lt;j){  //swap elems so that it is partitioned
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
      }
      else{ return j; } //return the boundary for this partition
    }
  }
  
  void quick_sort(int arr[], int start, int end){
     int boundary;
     if(start&lt;end){
           boundary = partition(arr,start,end);
  
           quick_sort(arr,start,boundary);
           quick_sort(arr,boundary+1, end);
     }
     return;
  }
  </code></pre>
  
  <p>The initial call is :  <code>quick_sort(a,0,n);</code> where <code>a</code> is an array of length <code>n</code></p>
  
  <p>This is the algo I'm trying to follow : (<code>p</code> and <code>r</code> are start and end indexes)</p>
  
  <pre><code>Partition(A,p,r)
      x &lt;- A[p]
      i &lt;- p-1
      j &lt;- r+1
      while (True) {
          repeat
              j &lt;- j-1
          until (A[j] &lt;= x)
          repeat
              i &lt;- i+1
          until (A[i] &gt;= x)
          if (i &lt;j) 
             exchange A[i] &lt;- A[j]
          else 
              return(j)
      }
  }
  </code></pre>
  
  <p>Looked at all of the possible instances where I could go wrong, not able to zero in on the issue.Thanks in advance for any help.</p>