0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @YuvalFilmus From what I can tell the first link doesn't have the code and I read and linked the 2nd link in the post already but couldn't figure it out based off of it. $\endgroup$ Commented Aug 11, 2023 at 20:07
  • $\begingroup$ The first link has the complete code — Algorithms 63 and 64. $\endgroup$ Commented Aug 12, 2023 at 13:04
  • $\begingroup$ You might want to check out Programming Pearls by Bentley (if you have not considered it). It could give additional insight. $\endgroup$ Commented Aug 13, 2023 at 19:16

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.