algorithm - 霍尔分区的正确性

Question

在 cormen 中给出的 Hoare 分区：

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

在快速排序中使用它时，以 {1,3,9,8,2,7,5} 作为输入，在第一个分区获得 {1,3,5,2,8,7,9} 之后，这是不正确的因为，所有小于枢轴的元素（这里是 5 ）都应该在左侧。有人可以指出我缺少什么吗？

Answer 1

算法是正确的。您正在A[p..r]使用A[p]作为枢轴对子数组进行分区。所以枢轴是1而不是5。

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

结果是：

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

在这种情况下，不会交换任何元素。

Answer 2

我面前没有 Cormen，但我很确定第一个循环中的比较应该是until A[j] < x- 如果是<=，您会将枢轴元素移动到左侧并将其留在那里（后面是较小的元素)，这就是您的示例中发生的情况。或者，第一个比较可能是<=，第二个比较可能是>- 只需确保枢轴元素不会被两个比较“捕获”。