Hoare分区陷入无限循环

我想写一个采用数组作为输入的Hoare分区函数，并将它与第一个元素一起分区（我知道这不是一个好主意，我应该使用随机化枢轴，像median-of-medians方法）。问题是这个函数在第一个元素最高时落入无限循环，如同数组[14,6,8,1,4,9,2,1,7,10,5]。在外层while的第一次迭代之后，我可以看到这个错误，i和j都等于10，因此循环将一直持续。我应该修补哪一部分以获得理想的效果？下面的代码：Hoare分区陷入无限循环

def hoare(arr): 
    pivot = arr[0] 
    i,j = 1,len(arr)-1 
    while i <= j: 
     while i < j and arr[i] < pivot: 
      i += 1 
     while j >= i and arr[j] >= pivot: 
      j -= 1 
     if i < j: 
      arr[i],arr[j] = arr[j],arr[i] 
    if j != 0: 
     arr[0],arr[j] = arr[j],arr[0] 
     return j

来源

2012-09-20 SexyBeast

首先，你的缩进显然是错误的，因为毕竟'如果我置于 abarnert

我根据编辑框中出现的位置缩进了“if”，因为使用了制表符和空格的组合来缩进原始文件。 – chepner

谢谢。你做得对。 – SexyBeast

我认为这个问题是您已转换使用do while（或重复，直到在霍尔的话来说）循环到while循环，所以它从来不第j个 - = 1.

Python中最简单的改造应该是改变两个内，而这样的循环：

while True: 
    i += 1 
    if not (i < j and arr[i] < pivot): break 
while True: 
    j -= 1 
    if not (j >= i and arr[j] >= pivot): break

（我这里假设if i < j:应该是第二个while循环外面，所有其他初始缩进都是正确的。）

我还没有完全说明这一点，或者进行了各种测试，但在翻译过程中可能不仅仅是这一个错误。您可能还需要将外部循环转换为do-while（Hoare实际上在末尾带有明确的while TRUE），但我不确定。无论如何，对于你的示例输入，修改后的版本返回9，arr是[10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5]，这是不正确的，但它解决了你的无限循环问题。

下一个问题是一个错误的错误。如果您要在内循环中首先执行+= 1和-= 1，则必须从-1,len(arr)而不是0, len(arr)-1（或如您所做的那样，1, len(arr)-1）开始。

可能还有其他问题。但我不想挖掘你的代码找到所有可能的错误并解释它们。如果您需要，请告诉我们我们的来源是什么，并解释您从该来源所做的每一次转换，并且解释出错的位置会更容易。如果不是的话，将Hoare的算法直接转换为Python就简单多了，然后希望你能弄明白。

这里的霍尔伪代码，我发现的一个副本在线（只是两个空格替换所有的选项卡）：

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 
     exchange A[i] ↔ A[j] 
    else 
     return j

这里有一个简单的翻译成Python;唯一的变化是小的语法（包括“交换”拼写的方式），并将每个重复/直到成为真/假。

def hoare(a, p, r): 
    x = a[p] 
    i, j = p-1, r+1 
    while True: 
    while True: 
     j -= 1 
     if a[j] <= x: 
     break 
    while True: 
     i += 1 
     if a[i] >= x: 
     break 
    if i < j: 
     a[i], a[j] = a[j], a[i] 
    else: 
     return j

对于具有相同签名你的函数：

def hoare0(arr): 
    return hoare(arr, 0, len(arr)-1)

来源

2012-09-20 21:06:21 abarnert

它怎么可能是正确的？5应该在最终分区的14之前。 – SexyBeast

Hoare分区陷入无限循环

回答

相关问题