Its well known that Lomuto's partitioning algorithm results in too many unnecessary swaps. Can we modify the algorithm in this way:
- Initialize a pointer a that points to the first position in the array, and initialize b to a.
- While the element at b is lesser than the pivot, Move B by 1.
- Set a = b.
- WHILE b doesn't reach the end of the array DO till STEP 7:
- IF element at b is greater than pivot, move b one step from left to right
- IF an element lesser than the pivot is found, swap the elements at b and a
- Increment a by 1 and b by 1.
I think this algorithm swaps only when necessary, unlike Lomuto's algorithm which swaps too many times, often needlessly. The time complexity should also be equivalent to Lomuto's algorithm, in both average as well as the worst-cases.
Does this algorithm correctly partition the array into elements less then the pivot and elements greater than the pivot? Does this algorithm use fewer swaps than Lomuto's algorithm?