Correctness of Hoare Partition

Question

Hoare partition as given in cormen:

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

when using this in Quick Sort, with {1,3,9,8,2,7,5} as input, after first partition getting {1,3,5,2,8,7,9}, which is not correct since, all elements smaller to pivot( here 5 ) should be on the left side. Can someone point out as to what I am missing?

Why is `i` initialized to be one *less* than the index of the partition? — Scott Hunter, Mar 03 '15 at 19:16
@ScottHunter: Because the loops are _repeat..until_ loops, so they will execute one iteration before checking the condition. Therefore, `i == p` during the first condition check. — Aasmund Eldhuset, Mar 03 '15 at 19:28
@AasmundEldhuset: which is pointless, since you know `A[p]==x`; the only way initializing `i=p` would be a problem would be if `p==r`, but then why call the function at all? — Scott Hunter, Mar 03 '15 at 19:38

score 0 · Answer 1 · answered Mar 03 '15 at 19:26

I don't have Cormen in front of me, but I'm pretty sure that the comparison in the first loop should be until A[j] < x - if it's <=, you'll move the pivot element to the left side and leave it there (followed by smaller elements), which is what happened in your example. Alternatively, the first comparison could be <= and the second could be > - just make sure that the pivot element won't get "caught" by both comparisons.

score 0 · Accepted Answer · answered Mar 03 '15 at 23:30

0

The algorithm is correct. You're partitioning the subarray A[p..r] using A[p] as the pivot. So the pivot is 1 and not 5.

Hoare-Partition(A=[1,3,9,8,2,7,5], p=0, r=6)

results in:

x = A[p] = 1
i = -1
j = 7

repeat:
   j = j - 1 = 6; A[j] = 5
   j = j - 1 = 5; A[j] = 7
   j = j - 1 = 4; A[j] = 2
   ...
   j = j - 1 = 0; A[j] = 1
   A[j] == x
repeat:
   i = i + 1 = 0; A[i] = 1
   A[i] == x
if i < j
   i == j, therefore return j

In this case, no elements are swapped.

answered Mar 03 '15 at 23:30

beaker

16,331
3
32
49

Thanks, I was taking the last element as the pivot. In that case, partition was not correct. Can't we use the same logic while taking the pivot as the last element? – hm5 Mar 09 '15 at 09:53
1

Sure, you can use the last element as the pivot, but you'll have to reverse the traversal order of the array, now scanning from left to right, and reverse all of the comparison operations. This is a very specialized in-place partition algorithm, not a generic one that would be useful for trying out different pivot selection strategies. – beaker Mar 09 '15 at 15:39
Absolutely correct - I wrongly converted it into a do-while loop while reading. Not often do I encounter a repeat-until loop these days. I deleted the comment to not confuse someone else who might be reading/or who did the same thing as me. – daniels_pa Sep 23 '20 at 22:33

Correctness of Hoare Partition

2 Answers2