7-1霍爾分區正確性證明

Question

我試圖解決CLRS（算法簡介）中的一些問題，並且在解決問題7-1時遇到了問題。部分b（現在），內容如下：

的索引i和j是使得我們從未訪問甲 的元件子陣列甲[P ... R]之外。

我該如何去證明它呢？我可以看到指數走向中間，但是......這真是扭曲了我的大腦。並解釋它不是一個證明。如果有人能夠解釋這個問題，我會非常感激。

Answer 1

相信你指的是下面的分區算法：

PARTITION(A,p,r) 
    x = A[p] 
    i = p-1 
    j = r+1 
    while TRUE 
    do repeat j=j-1 
     until A[j]<=x 
     repeat i=i+1 
     until A[i]>=x 
     if i<j 
     then exchange A[i] and A[j] 
     else return j 

的合適不變的while循環是總是存在的索引的，使得A [A] < = X和P < = a < j，以及使得A [b]使得A [b]> = x並且指數b爲< = r。

你需要顯示：

1. ，當循環開始是這樣（提示：選擇A = P和B = P）
2. ，如果這是在循環的開始真，那麼在循環結束時它仍然是真實的。 （提示：在交換過程中選擇a = j和b = i）

一旦建立了while循環的不變量，就可以考慮每個循環並顯示索引必須保持在允許的範圍內。 （提示：對於第一個重複循環嘗試證明j始終> = a，其中a如原始不變量中定義的那樣）