Hoare's Sort

[t2nator]

Where am I wrong with the breakdown on the algorithm?
For: 33 6 21 12 19 29 38 22 14 40

... what is the contents of array A after the first pass of Hoare's
version of the Partition method for the Quick Sort?

WHAT I GET: 14 6 21 12 19 29 38 22 33 40
ANSWER: 14 6 21 12 19 29 22 33 38 40

That should be after one pass, how are 38 and 33 swapped?

Logic:
i=start
k=end

move i until i > start
stop at 38 > 33
move k until k < start
stop at 14 < 33
swap
move i until i > start
i = 40 ends first pass

[cire]

I don't believe either of those sequences are correct.

The pseudo code for Hoare's partitioning alogrithm looks like:

H-PARTITION (A, p, r)
    pivot <- A[p]
    i <- p - 1
    j -> r + 1
    while true do
        repeat j <- j - 1 untilA[j] <= pivot
        repeat i <- i + 1 untilA[i] >= pivot
        if i < jthen
            exchange A[i] <-> A[j]
        else
            return j

Where A is the array to be sorted, p is the index of the first element and r is the index of the last element.

If you start with the array:

 0 1  2  3  4  5  6  7  8  9
33 6 21 12 19 29 38 22 14 40

then we have:

pivot = 33
i=-1
j=10

before the loop begins.

So, if we do j = j-1 until A[j] is <= 33, then we stop
when j is 8, and a[8] is 14.

Now, i = i+1 until A[i] is <= 33 - we stop when i = 0,
and a[0] is 33.

i is less than j, so we exchange A[i] and A[j]:

 0 1  2  3  4  5  6  7  8  9
14 6 21 12 19 29 38 22 33 40

we do j = j-1 until A[j] is <= 33, so we stop at j=7
where A[7] is 22.

we do i = i+1 until A[i] is >= 33, so we stop at i=6
where A[6] is 38.

i is less than j, so we exchange A[i] and A[j]:

 0 1  2  3  4  5  6  7  8  9
14 5 21 12 19 29 22 38 33 40

we do j = j-1 until A[j] is <= 33, so we stop at j=6
where A[6] is 22.

We do i = i+i until A[i] is >= 33, so we stop at i=7
where A[7] is 38.

i is not less than j, therefore we're done with the pass.
The array is:

 0 1  2  3  4  5  6  7  8  9
14 5 21 12 19 29 22 38 33 40

And what should be true is that all elements after A[j] are >= the pivot which was 33, and every other element should be less <= the pivot.