1

クイックソートのインプレース パーティション サブルーチンを実装しようとしていました。一意の要素の配列で動作しますが、配列に重複要素が含まれていると失敗します

コードは次のようになります

def inplace_partitioning(input,l,r):
    len_a=len(input)
    pivot=input[l]
    i=l+1
    for j in range(l+1,r+1,1):
        if input[j]<pivot:#do nothing if new elem >pivot
            #swap new elem with leftmost elem greater than pivot
            temp=input[j]
            input[j]=input[i]
            input[i]=temp
            i+=1
    #swap pivot with rightmost elem lessthan pivot
    temp=input[l]
    input[l]=input[i-1]
    input[i-1]=temp

入力が一意の要素の場合、コードは正しい結果を返します

input=[5,6,3,1,8,4]
inplace_partitioning(input,0,len(input)-1)
print input

>>[4, 3, 1, 5, 8, 6]

以下の配列を試したところ、間違った結果が得られました

input=[5,6,3,1,8,5]
>>>[1, 3, 5, 6, 8, 5]

これは私の実装に問題があるためですか?誰かが少し助けてくれますか?

4

3 に答える 3

0

私はあなたのアルゴリズムを完全には理解していません、そしてそれはクイックソートパーティショニングのようには見えません。通常、iとjは異なる方向に実行されます。一方は間隔の上部から開始し、もう一方は下部から開始しますが、私が正しく理解していれば、同じ方向に実行されます。最初の反復では、iとjの値は同じであり、ピボットよりも小さい場合は、それ自体と交換されます（つまり、ピボットよりも小さくない場合と同じ効果があります）。

于 2012-03-28T13:36:08.427 に答える
0 
if input[j]<pivot:

これは、数字が小さい場合にのみピボットの左に数字を移動することを意味します。ただし、ピボットのサイズに等しい数を移動する必要があります。そうしないと、ピボットと同じサイズの数がピボットの右側全体に広がります。

次のように変更します。

if input[j]<=pivot:
于 2012-03-28T07:32:30.650 に答える
0

これでできるはず

def partitionv(arr, l, r):

    p = r
    idx = l
    for i in range(l, r-1, 1):
        if arr[i] < arr[p]:
            arr[i], arr[idx] = arr[idx], arr[i]
            idx += 1
    arr[p], arr[idx] = arr[idx], arr[p]

    return arr

これは右側の要素のパーティションです。

于 2012-08-23T00:20:36.527 に答える