So I was reading the Hoare's partition part of the Quicksort wiki and it says:
"With respect to this original description, implementations often make minor but important variations. Notably, the scheme as presented below includes elements equal to the pivot among the candidates for an inversion (so "greater than or equal" and "less than or equal" tests are used instead of "greater than" and "less than" respectively; since the formulation uses do...while rather than repeat...until which is actually reflected by the use of strict comparison operators"
I read through the wiki section and the original paper but I'm not sure how to implement this original method. The part of the original method that I'm not sure about is:
"Hoare therefore stipulates that at the end, the sub-range containing the pivot element (which still is at its original position) can be decreased in size by excluding that pivot, after (if necessary) exchanging it with the sub-range element closest to the separation; thus, termination of quicksort is ensured."
It seems like the idea is to swap the pivot into a spot and then not include that index in the next sort, but how do we know where the actual pivot value is when using this method.
Can someone code up the original Hoare's method for me? This isn't homework or anything I was just studying leetcode and went down this rabbit hole after constantly running into edge cases when coding up Quicksort with Hoare's partition.
