当多个值等于枢轴时,Hoare 分区不起作用
Hoare partition not working when more than one value is equal to pivot
我正在尝试编写自己的霍尔分区函数以更好地理解它。我以为我很好地遵循了它的定义和伪代码,但即使它在很多情况下似乎都按预期工作,但当传入一个具有多个等于 pivot 的值的列表时,它会分崩离析并进入无限循环。我的错误在哪里,我应该如何修改它来修复错误?
def partition(lst, left_index, right_index):
pivot = lst[right_index]
while True:
#Increment left index until value at that index is greater or equal to pivot
while True:
if lst[left_index] >= pivot: break
left_index += 1
#Increment right index until value at that index is less or equal to pivot
while True:
if lst[right_index] <= pivot: break
right_index -= 1
if left_index < right_index:
lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
else:
return right_index
return partition(0, end)
您正在测试 lst[left_index] >= pivot
和 lst[right_index] <= pivot
中的枢轴值是否相等。这有效地防止了两个索引跳过枢轴值元素。因此,当两个或多个枢轴值元素被推向列表的中间时,left_index
和 right_index
会被无法逾越的障碍分开。删除其中 break
ing 行中的等号,不停机问题将消失。
但是,由于此更改,移动 left_index
的循环可能会将其推到 right_index
上方一个位置,甚至会在 right_index
停留在其初始位置时超出范围位置。类似地,移动 right_index
的循环可能会将其推到 left_index
下面一个位置,甚至在 left_index
停留在其初始位置时超出范围。为防止这种情况发生,您必须将这些循环中的 while True:
更改为 while left_index < right_index:
.
请注意,根据您是否删除 left_index
或 right_index
的相等性检查,分区会略有不同。当枢轴元素是列表中的最小值或最大值时,它对边界情况很重要。考虑到一开始 right_index
表示相对于输入范围的内部位置,而 left_index
指向边界位置,您必须允许 left_index
跳过枢轴值,而 right_index
必须被指示停止在枢轴值(相反的逻辑将使 left_index
保持在其初始位置直到算法结束,而 right_index
可以一直向下推到 left_index
,不产生任何分区)。
因此更正后的代码将是这样的:
def partition(lst, left_index, right_index):
pivot = lst[right_index]
while True:
while left_index < right_index and lst[left_index] <= pivot:
left_index += 1
while left_index < right_index and lst[right_index] > pivot:
right_index -= 1
if left_index < right_index:
lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
else:
return right_index
我正在尝试编写自己的霍尔分区函数以更好地理解它。我以为我很好地遵循了它的定义和伪代码,但即使它在很多情况下似乎都按预期工作,但当传入一个具有多个等于 pivot 的值的列表时,它会分崩离析并进入无限循环。我的错误在哪里,我应该如何修改它来修复错误?
def partition(lst, left_index, right_index):
pivot = lst[right_index]
while True:
#Increment left index until value at that index is greater or equal to pivot
while True:
if lst[left_index] >= pivot: break
left_index += 1
#Increment right index until value at that index is less or equal to pivot
while True:
if lst[right_index] <= pivot: break
right_index -= 1
if left_index < right_index:
lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
else:
return right_index
return partition(0, end)
您正在测试 lst[left_index] >= pivot
和 lst[right_index] <= pivot
中的枢轴值是否相等。这有效地防止了两个索引跳过枢轴值元素。因此,当两个或多个枢轴值元素被推向列表的中间时,left_index
和 right_index
会被无法逾越的障碍分开。删除其中 break
ing 行中的等号,不停机问题将消失。
但是,由于此更改,移动 left_index
的循环可能会将其推到 right_index
上方一个位置,甚至会在 right_index
停留在其初始位置时超出范围位置。类似地,移动 right_index
的循环可能会将其推到 left_index
下面一个位置,甚至在 left_index
停留在其初始位置时超出范围。为防止这种情况发生,您必须将这些循环中的 while True:
更改为 while left_index < right_index:
.
请注意,根据您是否删除 left_index
或 right_index
的相等性检查,分区会略有不同。当枢轴元素是列表中的最小值或最大值时,它对边界情况很重要。考虑到一开始 right_index
表示相对于输入范围的内部位置,而 left_index
指向边界位置,您必须允许 left_index
跳过枢轴值,而 right_index
必须被指示停止在枢轴值(相反的逻辑将使 left_index
保持在其初始位置直到算法结束,而 right_index
可以一直向下推到 left_index
,不产生任何分区)。
因此更正后的代码将是这样的:
def partition(lst, left_index, right_index):
pivot = lst[right_index]
while True:
while left_index < right_index and lst[left_index] <= pivot:
left_index += 1
while left_index < right_index and lst[right_index] > pivot:
right_index -= 1
if left_index < right_index:
lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
else:
return right_index