Quick Sort: Partition Algorithm

A post on quick sort is not particularly interesting for most developers. But, when you see more and more people using a complicated partitioning algorithm when explaining quick sort then, it is ok post a simpler partitioning algorithm. This algorithm and similar ones came in the Communications of the ACM and were retold by Bentley in his books. Still, they seem to be lost.
 
Quicksort works recursively by partitioning an array around a pivot element. So, after partitioning all the elements at indices less than the pivot's will be less the pivot itself. Those at indices greater than the pivot's index will be greater. Then, you repeat the same for elements on either side of the pivot. For example, if the array was 4, 19, 1, 3, 43, 45, 11, 2 and you say that, the pivot is 4 then, after partition around element 4, the array looks like this using this partition algorithm (explained further down).

2, 1, 3, 4, 43, 45, 11, 19

Then do quick sort on (2, 1, 3) 4 (43, 45, 11, 19). You get the idea.

So now comes the simpler partitioning algorithm. Here starting from the beginning
we keep track of elements greater than the pivot and whenever we see an element less than the pivot we replace the element which is greater than the pivot (we have it) with the one that is lesser.

So in our example if 4 was the pivot, 19 is the first element that is greater than the pivot, we go on to 1 and see that it is less than the pivot. We swap the two to get 4, 1, 19, 3, 43, 45, 11, 2. Now also we keep track of (index of) the first element that is greater than pivot. Again, we swap it for 3 and the array becomes 4, 1, 3, 19, 43, 45, 11, 2. Then, finally we meet 2 and then swap it for 19 and the array becomes 4, 1, 3, 2, 43, 45, 11, 19. So we have reached the end of the array. Our post condition is that, the pivot should be in such an index that, all elements to the left are less and those to the right are greater. This is achieved by simply swapping the pivot with our track index (here the index of 2). So we swap 4 and 2. Thus we get 2, 1, 3, 4, 43, 45, 11, 19.

Here is a snap of the partition code.

You can run the code in debug mode and see for yourself as to how this works.

The eclipse java project is available at theGoogle docs folder given below.

https://drive.google.com/folderview?id=0BxhHg0qy5gi4V2Q0ZlhrelZlOVU&usp=sharing