title: Quick sort Partition Logic using single traversal pointer versus two left and right pointer
body: <p>I have implemented quick sort as below. In the <strong>partition</strong> logic I have seen everywhere two pointers (by pointers I do not wish to refer to C/C++ pointers, but simple variables to traverse) are being used, one starts to traverse the array from start (looking for an element greater than pivot) and other from end (looking for an element smaller than pivot). </p>
  
  <p>The sum of elements traversed by both pointers is N, size of part of array passed to the partition logic.</p>
  
  <p>To make it easy I have just used single pointer and start traversing the elements from start till one step less than end where my pivot element lies. I assume my pivot position is in the start so I keep another variable to store my pivot-index. In case I find any element smaller than my pivot element then I do  a swap between my assumed pivot-index and my current traversed index and increment my pivot- index by 1. At the end of the loop I have position for my pivot ready, which I return. </p>
  
  <p><strong>I just wish to know If my approach has shortcomings over the approach where array passed to Partition logic is traversed from both ends [ find greater element in the left traversal and smaller in the right and then swap both , continue this until left and right traversal pointers cross each other ].</strong></p>
  
  <p>Kindly help. 
  Thanks &amp; Regards</p>
  
  <pre><code>package com.algorithm.sorting;
  
  public class QuickSort {
  
      public static void main(String[] args) {
              int a[] = { 5, 33, 45454, 43254, 2, 67, 8, 78, 8, 8, 8, 85654, 5, 4, -1, -1, 1, 234, 24, 43, 4, -7, 45, 4, -5,
                              544, 9, 8, 7, 6, 5, 4, 3, 2, 11, 2, 3, 4, 5, 6, 7, 8, 9 };
              quicksort(a);
              for (Integer i : a) {
                      System.out.println(i);
              }
      }
  
      public static void quicksort(int[] array) {
              quicksort(array, 0, array.length - 1);
      }
  
      private static void quicksort(int[] array, int start, int end) {
              if (start &lt; end) {
                      int pivotIndex = partition(array, start, end);
                      quicksort(array, start, pivotIndex - 1);
                      quicksort(array, pivotIndex + 1, end);
              }
      }
  
      private static int partition(int[] array, int start, int end) {
              int pIndex = start;
              int mid = start + ((end - start) / 2);
              int temp = array[mid];
              array[mid] = array[end];
              array[end] = temp;
  
              int pivot = array[end];
  
              for (int i = start; i &lt;= end - 1; i++) {
                      if (array[i] &lt; pivot) {
  
                              temp = array[i];
                              array[i] = array[pIndex];
                              array[pIndex] = temp;
                              pIndex++;
                      }
              }
              array[end] = array[pIndex];
              array[pIndex] = pivot;
              return pIndex;
      }
  
  }
  </code></pre>
  
  <p>(the program is same as i posted in <a href="http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-quicksort.html" rel="nofollow">http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-quicksort.html</a>, but now with this confusion in my mind I wish to correct my self and what I have posted) </p>