Hoare's partition takes the first element as the pivot and closes in from both ends. The left pointer advances while it sees values below the pivot, the right pointer retreats while it sees values above it; when they stop, the two offending values are swapped. When the pointers meet or cross, the right pointer's index j is returned: everything up to j belongs to the left part and everything after it to the right part.
Unlike Lomuto's scheme the pivot does not end up at the returned index; the two parts are merely separated.
Write hoare_partition(nums) which partitions the whole list in place and returns that split index.
Examples
Input: nums = [7, 2, 9, 1, 5]
Output: 2, and nums becomes [5, 2, 1, 9, 7]
Explanation: 5, 2 and 1 are at most 7; 9 and 7 are at least 7.
Input: nums = [3, 1, 2]
Output: 1, and nums becomes [2, 1, 3]
Constraints
1 <= len(nums) <= 10**5,-10**9 <= nums[i] <= 10**9- Partition in place.
- The tests call
hoare_result(nums), which runs your function and returns the pair(index, nums).
Goals
- Partition with pointers closing in from both ends
- Return a split point rather than the pivot's final position
- See why Hoare's scheme swaps less than Lomuto's