0

ここで説明するクイックセレクトを実装する小さなPythonコードがあります。

import random
def Quickselect(A, k):
    if not A:
        return
    pivot = random.choice(A)

    i = 0
    A1 = []
    A2 = [] # Two new arrays A1, A2 to store the split lists
    for i in range(len(A)):
        if A[i] < pivot :
            A1.append(A[i])
        else:
            A2.append(A[i])

    if k < len(A1):
        return Quickselect(A1, k)
    if k > len(A) - len(A2):
        return Quickselect(A2, k-(len(A) - len(A2)))
    else:
        return pivot
pass
def main():
    A = [45,1,27,56,12,56,88]
    print(Quickselect(A,2))
pass

randrangeエラーが発生しているようです。何かがおかしいですか？

編集：random.choiceの代わりに実装されrandom.randintます。上記のコードは正常に機能しているようです。UserBlenderに感謝します。

4

1 に答える 1

1

randrange範囲が空（つまり）のときに壊れるため、エラーが発生しますrandrange(1, 1)。

random.choice代わりに使用して、次のように変更しk <= len(A1)ますk < len(A1)。

def quick_select(A, k):
    pivot = random.choice(A)

    A1 = []
    A2 = []

    for i in A:
        if i < pivot:
            A1.append(i)
        elif i > pivot:
            A2.append(i)
        else:
            pass  # Do nothing

    if k <= len(A1):
        return Quickselect(A1, k)
    elif k > len(A) - len(A2):
        return Quickselect(A2, k - (len(A) - len(A2)))
    else:
        return pivot
于 2013-02-02T07:26:32.983 に答える