0

これは私のクイックソートアルゴリズムです。とてもシンプル

x = 0
def swap(list, a, b):
    temp = list[a]
    list[a] = list[b]
    list[b] = temp
    return list
def quicksort2(list, left, right):
    if right > left:
        global x
        x = x + 1
        print x , list, left, right
        l = left+1
        r = right
        while l <= r :
            while list[l] < list[left]:
                l = l + 1
            while list[r] > list[left]:
                r = r - 1
            if l < r:
                list = swap(list, l, r)
        list = swap(list, left, r)
        list = quicksort2(list, left, r-1);
        return quicksort2(list, r+1, right);
    return list

しかし、テストケースを実行すると

b = list([1, 2, 2, 3, 4, 5, 6, 12, 6, 32])
quicksort2(b, 0, len(b)-1)

結果は

1 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 0 9
2 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 1 9

そしてこれで停止します...誰もが何らかの理由があります...

4

2 に答える 2

0

私はあなたのコードを少し修正しました.いくつかの間違いが見つかりました.いくつかはすでに他の人によって言及されています. 残りは私が経験するつもりはありません。ただし、Python のリストは常に参照によって渡されるため、変更されたリストを返す必要はありません。

これは機能するはずです：

def quicksort2(list, low, high):
    global x
    x = x + 1
    print x , list, low, high

    l = low
    r = high
    mid = list[(r + l) / 2]
    while l <= r:
      while list[l] < mid: l += 1
      while list[r] > mid: r -= 1
      if l <= r:
        list[l], list[r] = list[r], list[l] #swap(r,l)
        l += 1
        r -= 1

    if r > low: quicksort2(list, low, r);
    if l < high: quicksort2(list, l, high);


if __name__ == '__main__':
  x = 0
  b = [1, 2, 2, 3, 4, 5, 6, 12, 6, 32]
  quicksort2(b, 0, len(b)-1)
  print b
于 2014-03-20T00:48:45.840 に答える
0

デバッガの下でプログラムの実行をトレースしようとしましたか...?

while l <= rループは永久に実行されます。r

  • left == 1
  • l == 2
  • r == 2

と

  • lはインクリメントされlist[2]ません。list[1]
  • rlist[2]は次の値よりも大きくないため、これ以上減分されませんlist[1]
  • lより小さくないため、スワップは行われませんr
  • lと等しいので、ループは続行されますr。
于 2014-03-19T23:55:20.223 に答える