We already know we have to divide an array into two sub-array for quicksort algorithm. Here I’ll describe how this partitioning actually works. If you want to know about how quicksort works, follow my other post on quicksort working principle. I followed Introduction to Algorithms, 3rd Edition (MIT Press)
The main idea of the partitioning is to select a pivot element(any element from the target array) and rearrange the array elements(including the pivot element) such that all the items to the left of the pivot element will be smaller or equal to it and all items to the right of the pivot element will be larger than the pivot element. For ease of implementation we can select the first item of the array as the pivot element, but it is not mandatory. We can select any item as pivot element. Best practice will be to randomly select a pivot element.
The partitioning is done with the help of two pointers: left & right. The left pointer will point to the leftmost item from the array and the right pointer will point to the rightmost item in the array. Then we select a random pivot element, and move the left pointer to the right direction as long as the item pointed by left pointer is smaller or equal to pivot element. We stop the left pointer when it points to an element that is larger than our pivot element. Similarly we move the right pointer to left direction as long as the item pointed by the right pointer is larger than the pivot element. We stop moving the right pointer when it points to an item smaller or equal to pivot element.
We display the above procedure with the help of the following images. We consider the 1st element(3 in our case) as the pivot element:
After a pass of the above algorithm, left pointer points to an element larger than the pivot element. Similarly right pointer points to an element smaller than the pivot element. So we can’t move them any further. But what if we swap the values of left and right pointer? Remember we’re not taking about moving the left or right pointer, we are only talking about swapping the values. If we do a swap we get the following scenario:
Now look at the new array after the swapping. The value of left pointer is smaller than the pivot element and value of right pointer is bigger than the pivot element. So we can use the previous approach again and move the left and right pointer further and get the following scenario:
Now look what happened here. The left & right pointer crossed over. At this point all items at and before right pointer is smaller or equal to pivot element. And all items from and after left pointer are bigger than the pivot element. So we get a position now to make the partition. All we have to do is swap the pivot element with the element at right pointer. This will make the new position of the pivot element as the partition point, because all items before the pivot will be smaller or equal to it and all items after the pivot will be bigger than it. Take a look of the swapping between pivot and right pointer:
So we swapped the pivot with the right pointer. So the right pointer value is now the pivot value and we can make a partition at this point and create two sub-arrays. But what is the intuition of making a partition here? It is actually very simple. Because all items before the right pointer is smaller than the pivot and all items after the right pointer is bigger than the pivot. Which means there is no way we could move our pivot to any more left or any more right. If the array was sorted, this would exactly be the position for our pivot element. So we can fix it here and make one sub-array consisting of the elements to the left of right pointer. And another sub-array will consists of elements to the right of right pointer.
This partitioning method is actually used for sorting an array. This sorting method is called QuickSort. All we have to do is repeatedly apply the same partitioning method on the sub-arrays.