0

わかった。あきらめる。中央値アルゴリズムの中央値を実装しようとしましたが、常に間違った結果が得られます。以下に多くのコードがあることは知っていますが、エラーを見つけることができず、コードの各チャンクにはかなりのプロセス設計があります。クイックソートは、中央値ピボット選択の中央値から取得した中央値を並べ替えるために使用するものです。簡単なクイックソートの実装である必要があります。getMean は、与えられたリストの平均を返すだけです。

getPivot は、ピボットを選択するために使用するものです。リストを実行し、一度に 5 つの整数を取り、それらの整数の平均を見つけ、その平均をリスト c に入れ、次に c の中央値を見つけます。これが、dSelect アルゴリズムに使用するピボットです。

dSelect アルゴリズムは、理論的には単純です。基本ケースは、リストが 1 項目の長さの場合に項目を返します。それ以外の場合は、quickSort と同じように、リストを反復処理します。現在の数字 j がピボットより小さい場合は、それをリスト i の左に移動し、i をインクリメントします。大きい場合は、リストの右側 i + 1 に移動し、i をインクリメントしません。これがリスト全体をループした後、ピボットを適切なインデックスに配置する必要があり、print ステートメントはそのことを示します。この時点で、ピボットが見つけようとしている位置よりも大きいか小さいかに応じて、左または右に再帰します。

この時点で、他にどの print ステートメントをテストすればよいかわかりません。そのため、このコードを突き刺すのに十分なほど献身的な人に頼っています。関連するトピックがあることは知っていますし、もっと多くの print ステートメントを実行できることもわかっていますが、信じてください。単純なアルゴリズムであるべきなのに、かなり困惑しました。

def quickSort(m, left, right):
    if right - left <= 1:
        return m
    pivot = m[left]
    i = left + 1
    j = left + 1
    for j in range(j, right):
        if m[j] < pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
        elif m[j] == pivot:
            m[j], m[i] = m[i], m[j]
    print m
    m[left], m[i-1] = m[i-1], m[left]
    m = quickSort(m, left, i-1)
    m = quickSort(m, i, right)
    print m
    return m
def getMedian(list):
    length = len(list)
    if length <= 1:
        return list[0]
    elif length % 2 == 0:
        i = length/2
        return list[i]
    else:
        i = (length + 1)/2
        return list[i]
def getPivot(m):
    c = []
    i = 0
    while i <= len(m) - 1:
        tempList = []
        j = 0
        while j < 5 and i <= len(m) - 1:
            tempList.append(m[i])
            i = i + 1
            j = j + 1
        tempList = quickSort(tempList, 0, len(tempList) - 1)
        c.append(getMedian(tempList))
    c = quickSort(c, 0, len(c) - 1)
    medianOfMedians = getMedian(c)
    return medianOfMedians

def dSelect(m, position):
    pivot = getPivot(m)
    i = 0
    j = 0
    if len(m) <= 1:
        return m[0]
    for j in range(0, len(m)):
        if m[j] < pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
        elif m[j] == pivot:
            m[j], m[i] = m[i], m[j]
        print "i: " + str(i)
        print "j: " + str(j)
    print "index of pivot: " + str(m.index(pivot))
    print "pivot: " + str(pivot) + " list: " + str(m)
    if m.index(pivot) == position:
        return pivot
    elif m.index(pivot) > position: 
        return dSelect(m[0:i], position)
    else:
        return dSelect(m[i:], position - i)
4

1 に答える 1

1

最大の問題は、次の行にあります。

i = (length + 1)/2

list = [1, 2, 3, 4, 5, 6, 7] の場合、答えは list[3] である 4 になります。バージョンは次のようになります。

i = (7 + 1) / 2

したがって、i は 3 ではなく 4 です。偶数長のリスト部分にも同様の問題がありますが、それほど大きな問題ではないはずです。

于 2012-11-15T05:24:40.123 に答える