0

このプログラムでは、挿入ソートでデータ比較の回数を計算したいのですが、コードが期待どおりに動作しません。

def insertionSort(list):
    numOfComp = 0
    for i in range(1,len(list)):
        value = list[i]
        j = i - 1
        while j>=0:
            if value < list[j]:
                list[j+1] = list[j]
                list[j] = value
                j = j - 1
                numOfComp += 1
            if value >= list[j]:
                numOfComp += 1
                j = j - 1
            else:
                break
    print("Number of data comparisons:",numOfComp)
    print("Sorted list:",list)
4

2 に答える 2

1

問題は

if value >= list[j]:
     numOfComp += 1
     j = j - 1

value >= list[j]whileループを終了し、それ以上のcomarisonを停止することができ、またそうすべきである場合

また、比較を2回繰り返しています 次の洗練されたコードを参照してください

def insertionSort(list):
    numOfComp = 0
    for i in range(1,len(list)):
        value = list[i]
        j = i - 1
        while j>=0:
            if value<list[j]:
                flag=True
            else :
                flag=False
            numOfComp += 1
            if flag:
                list[j+1] = list[j]
                list[j] = value
                j = j - 1
            else:
                break
    print("Number of data comparisons:",numOfComp)
    print("Sorted list:",list)
于 2013-10-31T03:09:15.830 に答える
0

ループ ヘッダーは、終了条件と呼ばれるループ本体よりも +1 実行されることを忘れないでください。次の例を見てください。

S = 0;
for(int i = 0; i < 5; i++) {
    S++;
}

S++ は5 回実行されますが、i < 5は 6 回実行されます。最後の 1 つは i < 5 かどうかをチェックすることで、false を見つけてループを終了します。

于 2014-11-19T09:28:02.863 に答える