title: Partitioning an array on a Pivot
body: <p>I am trying to write a simple algorithm for moving the elements around pivot such that the  elements on the left of pivot is smaller than the pivot and the element on the right of pivot is greater than it (the same step in quick sort). I have written code that works, but after that I changed the algorithm to the below, and it is not working.</p>
  
  <p>The idea of the algorithm is simple.</p>
  
  <blockquote>
    <p>Have two pointers, one at the beginning of the array and one at the end of array. If the elements pointed by i are lesser than pivot, keep skipping it until we find a greater element; and keep decrementing j until we find an element greater than the smaller element. [It is a common algorithm]</p>
  </blockquote>
  
  <p><strong>Now the code</strong></p>
  
  <pre><code>private  static void sortByPivot(int[] a)
  {
  
      Random r = new Random();
      int index = r.nextInt(a.length);
      int pivot = a[index];
  
      System.out.println("pivot = " + pivot);
  
      int i =0 , j = a.length -1;
  
      while(true)
          {
  
              while(a[i] &lt;= pivot) i++;
  
              while( j &gt;0 &amp;&amp; a[j] &gt;= pivot) j--;
  
              if(i &lt;= j)
              {
                  break;
              }
              else{
                  swap(a,i,j);
                 }
  
          }
  
          swap(a,i,index); //swap the pivot and the i
  }
  </code></pre>
  
  <p>Swap routine :</p>
  
  <pre><code>private static void swap(int[] a, int i , int j)
  {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
  }
  </code></pre>
  
  <p>When I run this with the following array</p>
  
  <pre><code>  int[] a = {46,3,8,4,2,6,244,76} 
  </code></pre>
  
  <p>and when the pivot is picked as 4
  the output is</p>
  
  <pre><code>         4 3 8 46 2 6 244 76 
  </code></pre>
  
  <p>For some other pivots that are in the edge, I get a null pointer exception.</p>
  
  <p>Is there any flaw in the implementation. The logic seems right to  me.  I have been trying it for quite sometime but I am unable to fix it.</p>