All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode.
p is what is returned by the
partition function, Hoare divides his array from
p and from
hi, while Lomuto divides his array from
p-1 and from
I may be wrong about this, but Quicksort's philosophy is...
- Take an element in the subarray (pivot).
- 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.
- 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.
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
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 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
p-1 and from
hi. But, I can't understand how Hoare can divide his array from
p and from
hi, make up for his partition not putting its pivot in its rightful place.