2

配列を入力として受け取り、最初の要素をピボットとして分割する Hoare 分割関数を作成しようとしています (median-of-mediansアプローチのようにランダム化されたピボットを使用する必要があることはわかっています)。問題は、この関数が配列のように最初の要素が最大のときに無限ループに陥ること[14,6,8,1,4,9,2,1,7,10,5]です。outer の最初の繰り返しの後while、両方とも10iにj等しいため、エラーが表示されるため、ループは永遠に続きます。望ましい効果を得るには、どの部分を修復すればよいですか? コードは次のとおりです。

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
4

3 に答える 3

2

問題は、do-while (Hoare の用語では、repeat-until) ループを while ループに変換したため、最初の j -= 1 が実行されないことにあると思います。

Python での最も単純な変換は、内側の 2 つの while ループを次のように変更することです。

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:が 2 番目の while ループの外側にあると想定しており、他の最初のインデントはすべて正しいと想定しています。)

私はこれを完全に推論したり、さまざまなテストを実行したりしていませんが、あなたの翻訳にはおそらくこの 1 つのエラーだけではありません. また、外側のループを do-while に変換する必要があるかもしれません (Hoare は実際にwhile TRUEは最後にチェックを付けて明示的にしています)が、私にはよくわかりません。とにかく、サンプル入力の場合、変更されたバージョンは を返し9、これarrは[10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5]正しくありませんが、無限ループの問題は解決します。

次の問題は、off-by-one エラーです。内側のループで最初に+= 1andを実行する場合は、 (または、行ったように)ではなく、 から開始する必要があります。-= 1-1len(arr)0, len(arr)-11, len(arr)-1

まだ他の問題があるかもしれません。しかし、コードを掘り下げて、考えられるすべての間違いを見つけて説明したくはありません。それが必要な場合は、私たちのソースが何であったかを教えてください。また、そのソースから行った各変換について説明してください。そうでない場合は、Hoare のアルゴリズムを直接 Python に変換する方がはるかに簡単です。

オンラインで見つけた Hoare 疑似コードのコピーを次に示します (すべてのタブを 2 つのスペースに置き換えただけです)。

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 への簡単な翻訳です。唯一の変更点は、小さな構文 (「exchange」の綴り方を含む) と、各 repeat/until を while True/break に変更することです。

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-20T21:06:21.770 に答える