2

ここ 2 日間ほどクイックソートを実装しようとしています (私のプログラミング スキルが錆びてきているようです)。何が間違っているのかわかりません。諦めかけたので掲示板に相談しようと思いました。

ここに私がPythonで実装しようとしているコードがあります。しかし、それは望ましい結果を与えていません。誰でも私が間違っていることを指摘できますか?

def QuickSort(A,p,r):

if p < r:
    pivotIndex = Partition(A,p,r)
    QuickSort(A,p,pivotIndex-1)
    QuickSort(A,pivotIndex+1,r)
    return A
def Partition(A,p,r):

m = A[p]
i = p+1
for j in range( p+1 , r ):
    if A[j] < m:
        A[j] , A[i] = A[i] , A[j]
        i+=1
A[p], A[i-1] = A[i-1] , A[p]
return i-1

テスト入力の出力は次のとおりです。

>>>QuickSort([9,8,7,6,5,4,3,2,1],0,9)
[1, 3, 5, 6, 7, 4, 8, 2, 9]

誰かがこれを実装するのを手伝ってくれたら、とても感謝しています。

よろしく

4

4 に答える 4

2

スライスしても元のリストのビューは返されません。古いリストのデータから新しいリストを作成します。つまり、再帰呼び出しQuickSortは元のリストを変更しません。

于 2013-07-15T17:22:04.940 に答える
1

この実装を 1 行のコードで試すことができます。

def QuickSort(list):
    return [] if list==[]  else QuickSort([x for x in list[1:] if x < list[0]]) + [list[0]] + QuickSort([x for x in list[1:] if x >= list[0]])

print QuickSort([9,8,7,6,5,4,3,2,1])
于 2013-07-15T17:25:47.023 に答える
1

私は答えを見つけました。QuickSort メソッドに one-less を渡していたようです

def QuickSort(A,p,r):
    if r-p <= 1: return
    pivotIndex = Partition(A,p,r)
    QuickSort(A,p,pivotIndex)
    QuickSort(A,pivotIndex+1,r)
    return A
def Partition(A,p,r):

    m = A[p]
    i = p+1

    for j in range( p+1 , r ):
        if A[j] < m:
            A[j] , A[i] = A[i] , A[j]
        i= i + 1
    A[p], A[i-1] = A[i-1] , A[p]
    return i-1

正しい実装です

于 2013-07-15T18:33:42.307 に答える
0

左側にピボットを残してスキップしたかったようですが、うまくいかなかったので、配列の最後に移動し、それに応じて反復インデックスを減らしてから、ポストパーティションを逆にしましたスワップ (ピボットの動きを考慮するため)。

def Partition(A,p,r):

  m = A[p]
  A[p], A[r] = A[r], A[p]
  i = p
  for j in range( p, r ):
    if A[j] < m:
        A[j] , A[i] = A[i] , A[j]
        i+=1
  A[r], A[i] = A[i] , A[r]
  return i

左側のピボットでそれを行うことができると思いますが、ループの方向を変更する必要があると思いますが、よくわかりません.

編集:申し訳ありませんが、呼び出しを追加するのを忘れていましたが、インデックスは現在包括的であるため、 QuickSort([9,8,7,6,5,4,3,2,1],0, 8 ) です。

于 2013-07-15T18:33:36.990 に答える