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.

  • $\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 Nov 28 '17 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.