1
$\begingroup$

I'm tracing through a quick sort algorithm on paper, but I keep getting stuck on the partitioning using Hoare's partitioning. The array is {3,1,4,1,5,9,2,6,5,3,5}. I'm using median of three for the pivot, so pivot is 5, I swap the pivot with the left and have {5,1,4,1,5,9,2,6,5,3,3}. I go through the algorithm as follows

  1. Swap A[4] with A[10]: A= {5,1,4,1,3,9,2,6,5,3,5}
  2. Swap A[5] with A[10]: A= {5,1,4,1,3,5,2,6,5,3,9}
  3. Swap A[5] with A[9]: A= {5,1,4,1,3,3,2,6,5,5,9}
  4. Swap A[7] with A[9]: A= {5,1,4,1,3,3,2,5,5,6,9}

So I have the pointers stuck on the the two 5's at A[7] and A[8], but Hoare's keeps telling me to flip those two because i < j so I have to keep flipping. I know there's something I'm doing wrong, but I don't understand what it is.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ This is basically debugging pseudocode for a specific version of quicksort. We cannot really help you unless you tell us your pseudocode. There might be a small error in the pseudocode, or perhaps you're misunderstanding something. Try to understand what the algorithm is trying to do, and correct it accordingly. $\endgroup$
    – Yuval Filmus
    Commented Nov 28, 2017 at 11:42

1 Answer 1

Reset to default
2
$\begingroup$

Since your pivot value is 5, the comparison with A[7] and A[8], which are both 5, will be =pval.

While you didn't share the pseudocode you used, I believe you used a while loop for incrementing/decrementing the pointers. This means the pointers will just be stuck at A[7] and A[8] as they do not satisfy the expressions <pval or >pval.

Instead of using a while loop, you should pre-decrement the left pointer and pre-increment the right pointer, then use a do-while loop. This will ensure that the pointers will increment/decrement at least once even if it is =pval.

This website has an implementation of both Hoare's and Lomuto schemes. https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow, very good observation. While implementing a quicksort I got rid of this do-while in preference of for because I thought it's just a micro-optimization to do one less comparison each cycle, but then that requires you to pass out of boundaries indices or pointers, which is kinda annoying. Turns out it's a guard against a case where all elements are the same. $\endgroup$
    – Hi-Angel
    Commented Nov 9, 2023 at 16:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.