This is the pseudocode on wikipedia for Hoare's partitioning scheme:
algorithm partition(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i] < pivot //Question here do j := j - 1 while A[j] > pivot if i >= j then return j swap A[i] with A[j]
This code finds an inversion and swaps it. Now, the problem of partitioning about a pivot is to divide an array such that all elements <= pivot fall in one partition, and all elements > pivot fall in the other.
My question is simple: why not use
while a[i] <= pivot ?
As far as I can tell, it will work correctly, infact it would align better with the previous definition of partitioning.
If it does work, the big question is why wasn't it used in the original paper? It makes more sense and seems to be slightly faster as well (less number of swaps required).
Infact, while we're on the subject: would it be incorrect to also use
while A[j] >= pivot that could further reduce the number of swaps.
I know that if I'm too worried about multiple elements repeating I should use 3 way partitioning, but I'm curious about how this algorithm would work nonetheless.