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?
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.