There are two commonly mentioned partition methods:
algorithm lomuto_partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
if A[j] ≤ pivot then
i := i + 1
swap A[i] with A[j]
swap A[i+1] with A[hi]
return i + 1
algorithm hoare_partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j - 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
(excerpt from Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms. MIT Press and McGraw-Hill. pp. 170–190.)
And it has been suggested that Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.
But why does Lomuto partitioning scheme use rightmost element(A[hi]) as pivot value and Hoare scheme use leftmost element (A[lo]) as pivot value?
It seems that there is no difference in number of comparisons or swaps and they will produce worst case behavior on already sorted arrays.
Is it just because they implemented and introduced them with rightmost element and leftmost element as pivot value respectively? Or is there a reason?