Now we discuss its algorithm.
In figure 1, you can see that we divided the space into 3 sections: unknown elements (u), greater elements (>) and less than equal to elements(<=). We also use 2 pointers i and j which are initially at the first element of the array.
Now we define these 3 areas for iteration purposes. The less than equal elements are in the area 0 to j-1, the greater elements are in the j to i-1 area and the unknown elements are in the i to end area as shown by Figure 2.
As you can see in the figure, at the moment when i is at the first element, i to the end covers the entire array. Hence, all the elements that are unknown right now are depicted by drawing a line across those elements.
Since j and i are at the same element then there is no area from j to i-1. So right now we don't have any element greater than the pivot.
Now for the main algorithm, we analyse arr[i]. If arr[i]>pivot then i is increased by 1 which means the unknown area is decreased by one and the area for greater elements is increased.
Else if arr[i]<=pivot, then we swap the elements at i and j and increment both i and j by one.Why do you think it is done?
This decreases the unknown area by one element, less than or equal to area increases and the size of the greater than area remains the same but the area gets shifted forward.
Why do we do all this? Our main aim is to totally finish the unknown area so that all the elements get partitioned into the appropriate sides.
Now that we have understood the algorithm and its working we try to write the code for the same.