霍尔分区的正确性
Correctness of Hoare Partition
在 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
在快速排序中使用它时,以 {1,3,9,8,2,7,5} 作为输入,在第一个分区得到 {1,3,5,2,8,7,9} 之后,这是不正确的,因为所有小于枢轴的元素(此处为 5 )都应位于左侧。有人可以指出我遗漏了什么吗?
我面前没有 Cormen,但我很确定第一个循环中的比较应该是 until A[j] < x
- 如果是 <=
,你将移动将元素旋转到左侧并将其留在那里(后面是较小的元素),这就是您的示例中发生的情况。或者,第一个比较可以是 <=
,第二个可以是 >
- 只需确保主元素不会通过两次比较得到 "caught"。
算法正确。您正在使用 A[p]
作为基准对子数组 A[p..r]
进行分区。所以枢轴是 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
在这种情况下,没有元素被交换。
在 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
在快速排序中使用它时,以 {1,3,9,8,2,7,5} 作为输入,在第一个分区得到 {1,3,5,2,8,7,9} 之后,这是不正确的,因为所有小于枢轴的元素(此处为 5 )都应位于左侧。有人可以指出我遗漏了什么吗?
我面前没有 Cormen,但我很确定第一个循环中的比较应该是 until A[j] < x
- 如果是 <=
,你将移动将元素旋转到左侧并将其留在那里(后面是较小的元素),这就是您的示例中发生的情况。或者,第一个比较可以是 <=
,第二个可以是 >
- 只需确保主元素不会通过两次比较得到 "caught"。
算法正确。您正在使用 A[p]
作为基准对子数组 A[p..r]
进行分区。所以枢轴是 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
在这种情况下,没有元素被交换。