Does Hoare partioning fail in some cases?

Question

Was working on a Hoare partitioning problem and realized that Hoare Partitioning seems to fail to sort items properly in the case where the left and right pointers both encounter a value equal to the pivot at the same time.

For example for the array [0,2,1,0,2,1,2,0] if you were to pick 1 as the pivot, the left and the right pointers would encounter the two 1's at the same time, swap them, then continue on, giving an incorrect output of [0,0,1,0,2,1,2,2]

Is this known to be an issue with Hoare partitioning? How do people usually deal with this case?

For reference, this is the code I am using:

def hoarePartition(nums):
    left, right = -1, len(nums) 
        while True:
            left += 1
            while nums[left] == 0:
                left += 1
            right -= 1
            while nums[right] == 2:
                right -= 1
            if left >= right:
                return
            nums[left], nums[right] = nums[right], nums[left]

Answer 1

The purpose of partitioning is not to sort the elements, but to split (a.k.a. partition) them into two nonempty groups, one where the elements are less than or equal to the pivot element and one where the elements are greater than or equal to the pivot element. (Hoare partitioning allows either group to contain elements that are equal to the pivot, while Lomuto partitioning puts all the equal-to-pivot elements in the right group. Quicksort can handle either result, but it is important that neither group is empty; otherwise, Quicksort might recurse infinitely without ever being able to split the list into smaller parts.)

Given this, we see that your example output is valid: the algorithm stops in the middle, and all the values in the left half are less than or equal to 1, and all the elements in the right half are greater than or equal to 1. The order within the partitions doesn't matter; it's Quicksort's job to actually sort the numbers.

However, there are a few issues with your implementation:

• Comparing to 0 and 2 works if the only values are 0, 1, and 2. In the general case, you need to instead compare to the value of the pivot element.
• Thus, the pivot selection needs to be baked into your code. It should be the element in the middle, or to the left of the middle if there's an even number of elements.
• You need to return right, which indicates where the split between the two groups is.