1. ホーム
  2. python

[解決済み] Python 3: 挿入ソート比較カウンタ

2022-02-06 09:35:58

質問

挿入ソートプログラムに比較の合計カウンターを追加する必要があるのですが、なぜ比較の合計が0になるのかわかりません

比較の出力が0ではなく、15(私の特定の配列の場合)であるべきだということは分かっています。

これが今までの私のコードです。

def insertionSort(values):
    k = 0
    n = len(values) - 1
    comparisons = 0
    while k+1 <= n:
        i = k
        while values[i] > values[i+1]:
            temp = values[i]
            values[i] = values[i+1]
            values[i+1] = temp
            comparisons += 1 #I think this is wrong
        k = k + 1
    return comparisons, values

何が間違っているのでしょうか?

どのように解決するのですか?

あなたのコードをチェックしたところ、[7,5,4,6]をソートする目的が達成されていません。

以下はその修正版です。

def insertionSort_mod(values):
    k = 0
    n = len(values) - 1
    comparisons = 0
    while k+1 <= n:
        i = k+1
        curr_val = values[i]
        comparisons += 1
        while i>0 and values[i-1] > curr_val:
            values[i] = values[i-1]
            i=i-1
            comparisons += 1
        values[i] = curr_val
        k = k + 1
    return comparisons, values

print insertionSort_mod( [1, 2, 3, 55, 5, 6, 8, 7, 9, 111])

これを出力する。

(15, [1, 2, 3, 5, 6, 7, 8, 9, 55, 111])

k+1 は現在のインデックスなので、i は k+1 となり、前の値 i-1 と比較されるはずです。