### Hoare's Sort

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
Last edited on
I don't believe either of those sequences are correct.

The pseudo code for Hoare's partitioning alogrithm looks like:
 ``1234567891011`` ``````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:

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

then we have:
 ``123`` ``````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]:
 ``12`` `````` 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]:
 ``12`` `````` 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:

 ``12`` `````` 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.
Last edited on
Topic archived. No new replies allowed.