Selection of pivot in quicksort partitioning of Hoare and Lomuto

Question

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?

Answer 1

As you now correctly, every arbitrary but fixed choice of pivot is equally bad; the cases are symmetric.

The difference is probably historical and may not exist in all write-ups of the algorithms.

Note that you have to change the for-loops if you switch from hi to lo or the other way around, but that is not a conceptual difference.