How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?

Question

All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode.

If p is what is returned by the partition function, Hoare divides his array from lo to p and from p+1 to hi, while Lomuto divides his array from lo to p-1 and from p+1 to hi.

I may be wrong about this, but Quicksort's philosophy is...

1. Take an element in the subarray (pivot).
2. Rearrange the subarray in such a way that all elements left of the pivot are smaller than the pivot, and all the elements right of the pivot are greater than the pivot.
3. Divide the array about the pivot. Repeat the process for the two smaller sub-subarrays. Keep doing this until you encounter an array with only one or less elements, because that is already sorted.

I find Hoare's partition to be more simpler to understand, than Lomuto's. Hoare's partition simply instructs us to start from the left end and the right end and to keep moving towards each other. If left marker encounters an element greater than the pivot, then the left marker pauses, and waits for the right marker to find an element smaller than the pivot. Then they exchange the elements, so that the left marker has the smaller element, and the right marker has the greater element. They keep doing this until they meet. Very straightforward.

Lomuto's partition, can be considered as a snake, of sorts, made of two parts, a head and a tail. The pivot is fixed (I usually take the last element as the pivot for Lomuto). The snake starts from the left-hand side, and stops just before the last element. When the snakes encounters an element smaller than the pivot, that element goes to the tail and the length of the tail increases. When an element greater than the pivot is discovered, that element goes to the head of the snake. Finally, the pivot is placed between the tail and the head. It's pretty clear but not as intuitive or efficient (in some cases) as Hoare's partition.

What confuses me is that Hoare's partition doesn't ensure that the position of the pivot after the partition has run its course, will be it's position in the final, sorted array. The only pattern that I could recognise in Hoare's partition was that i is at the final position of the pivot and that j is either i or i-1, j and i being the right and left markers.

Lomuto's partition, however, guarantees it. So, when I step back and look at the bigger picture, it makes sense for Lomuto to divide the array from lo to p-1 and from p+1 to hi. But, I can't understand how Hoare can divide his array from lo to p and from p+1 to hi, make up for his partition not putting its pivot in its rightful place.

Answer 1

I've been looking into examples and sorting arrays myself via Hoare's quicksort. I think I've found another interesting pattern in Hoare's partition algo. Which may explain why Hoare's method works. Lomuto divides the array into three parts; elements smaller than the pivot, the pivot, elements greater than the pivot. I think Hoare looks at things differently. He divides the array into two parts; elements smaller than the pivot, elements equal to or greater than the pivot. One of the traps that I fell into was that Lomuto's partition returns the final position of the pivot, whereas Hoare's partition returns the position just before the final position of the pivot. This is why Lomuto then quick sorts from lo to p-1, whereas Hoare quick sorts from lo to p. Another inference that can be drawn is that if Hoare's partition returned i instead of j, we'd then divide the array into two parts- from lo to i-1 and from i+1 to hi, just like Lomuto did. And it only took me 4 hours to understand that.