Hoare分區陷入無限循環

Question

我想寫一個採用數組作爲輸入的Hoare分區函數，並將它與第一個元素一起分區（我知道這不是一個好主意，我應該使用隨機化樞軸，像median-of-medians方法）。問題是這個函數在第一個元素最高時落入無限循環，如同數組[14,6,8,1,4,9,2,1,7,10,5]。在外層while的第一次迭代之後，我可以看到這個錯誤，i和j都等於10，因此循環將一直持續。我應該修補哪一部分以獲得理想的效果？下面的代碼：

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 

Answer 1

我認爲這個問題是您已轉換使用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)