# Hoare's Partition Scheme Stuck

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.

• 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. – Yuval Filmus Nov 28 '17 at 11:42