title: QuickSort partition algorithm
body: <p>I am trying to program the quicksort algorithm from Cormen Algorithm Textbook. Below is my code.</p>
  
  <pre><code>class Quicksort
  {
      public void qSort(int[] a, int p, int r)
      {
          if(p&lt;r)
          {
              int q = Partition(a, p,r);
              qSort(a, p, q-1);
              qSort(a, q+1, r);
          }
       }
  
       private int Partition(int[] a, int p, int r)
       {
           int x = a[r];
  
           int i = p-1;
           int temp=0;
  
           for(int j=p; j&lt;r-1; j++)
           {
               if(a[j]&lt;=x)
               {
                   i++;
                   temp = a[i];
                   a[i] = a[j];
                   a[j] = temp;
               }
           }
  
           temp = a[i+1];
           a[i+1] = a[r];
           a[r] = temp;
           return (i+1);
       }
  }
  
  public class QuickSortTest
  {
       public static void main(String[] args)
       {
           Quicksort qsort = new Quicksort();
           int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};
  
           System.out.print("Original  Array : ");
           for(int i=0; i&lt;array.length;i++)
           {
               System.out.print(array[i] + " ");
           }
  
           int length = array.length;
  
           qsort.qSort(array, 0, length-1);
  
           System.out.print("Sorted  Array : ");
           for(int i=0; i&lt;array.length;i++)
           {
               System.out.print(array[i] + " ");
           }
       }
  }
  </code></pre>
  
  <p>But, I am getting a wrong output when I execute this code. </p>
  
  <pre><code>Original  Array : 5 4 7 2 1 9 3 6 10 8 
  Sorted  Array : 1 4 5 2 6 7 3 8 9 10 
  </code></pre>
  
  <p>Can anyone please explain what is wrong. I have implemented this code exactly as given in "Introduction to algorithms" book. Thank you.</p>