0

リスト内の m 番目に小さい数値を見つけるために、クイック選択を実装しようとしました。プログラムを実行すると、同じ配列で正しい値が返されることもあれば、間違った値が返されることもあります。私は何を間違っていますか 彼女はコードです

def select_mth_smallest(A, m):
    pivot = np.random.choice(A)
    # split into 3 partitions
    A1 = [] 
    A2 = []
    A3 = []
    for item in A:
        if item < pivot:
            A1.append(item)
        if item > pivot:
            A3.append(item)
        else:
            A2.append(item)
    #find where m'th largest element is and recurse accordingly
    if len(A1) >= m:
        return select_mth_smallest(A1, m)
    elif (len(A1) + len(A2)) >= m:
        return pivot
    else:
        return select_mth_smallest(A3,m - (len(A1)+len(A2)))

これは、アルゴリズムが失敗する入力です。

A = [1,2,3,4,5]

select_mth_smallest(A,5)

上記のステートメントを繰り返し実行すると、5 (正しい) と 4 (正しくない) が交互に表示されます。

私を特に困惑させることの 1 つ (私は Python を初めて使用します) は、同じ入力を繰り返したときに関数の戻り値が異なる理由です。かなり散発的に見えます..ところで、私はJupyterを使用しています

4

1 に答える 1

2

複数のパーティションにいくつかのアイテムを追加しています。

    if item < pivot:
        A1.append(item)
    if item > pivot:
        A3.append(item)
    else:
        A2.append(item)

A1ピボットよりも少ないアイテムのセットです。A3ピボットより大きいアイテムのセットです。A2ただし、 2 番目のステートメントはすべてのアイテムに対して実行され、いずれかの分岐が実行されるため、ピボット以下のアイテムのセットです。if

ここでは、 and句を含む単一のifステートメントが必要です。elifelse

    if item < pivot:
        A1.append(item)
    elif item > pivot:
        A3.append(item)
    else:
        A2.append(item)
于 2016-05-02T20:50:26.233 に答える