アルゴリズムイントロダクション¹を読み進めていくシリーズ。

前回は実装したソートをテストする関数 is_sorted を実装した。

今回は「挿入ソート」の実装を行おう。

挿入ソート

アルゴリズム

トランプを使って遊ぶところを思い浮かべてみよう。各プレイヤーには1枚ずつカードが配られていく。大概の人は手札の番号は昇順に並べていくだろう。

手順として以下の具合だ。

配られたカードを右手で受け取り、カードの数字を確認する。
左手に持っている手札の各数字を右のカードから確認していき、新たなカードを挿入する位置を決定する。
新たなカードを手札に挿入する。
以上を繰り返す。

これはまさに挿入ソートである。

実装

本書中の疑似コードを元にPythonによる実装を行う。擬似コードでは配列のインデックスが1から始まっているが、Pythonの配列ではインデックスは0から始まる。そのため疑似コードと下記のコードで、インデックスがずれていることには注意してほしい。

コードは次のとおりである。

from test_sort import is_sorted


def insertion_sort(A):
    """挿入ソートを行う関数。
    アルゴリズムイントロダクションでの挿入ソートの擬似コードを素直に実装している。

    Args:
        A (list of numbers): 数値のリスト
    """

    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key


if __name__ == "__main__":
    import numpy as np

    numbers = np.random.randint(255, size=10)
    print('ソート前:', is_sorted(numbers), numbers)
    insertion_sort(numbers)
    print('ソート後:', is_sorted(numbers), numbers)

12行目 : j を1から (A の長さ - 1) まで増分していくループである。
- このループは j 枚目のカードを受け取るという意味である。
- j は 1 から始まっているので、初めから左手の手札には既に 1 枚のトランプがあるというわけである (インデックスは 0 から始まるため) 。
- なぜかというと、手札が1枚しかなければ順番も何もなく、既にソート済みであり処理が不要だからである。
13行目 : key に A[j] を代入する。
- A[j] とは新たに受け取ったトランプの数字である。
14 - 17行目 : i を j - 1 から 0 まで減分していくループである。
- 0 と j - 1 とは既にソートされた手札の範囲を示している ( A[0 .. j -1] はソート済み) 。
- 15行目の A[i] > key により、カードの挿入位置に到達したときにはループを抜ける。
  - 正確には、ループを抜けるときに i は "挿入位置 - 1" となっている (ループを抜けるのは A[i] <= key となったときであるため、挿入位置を1だけ通り過ぎる) 。
- それと同時に、手札のカードを1つずつ右の位置に移動していく (16行目) 。
18行目 : 上記ループで見つけた挿入位置に対して key を挿入する。
- 挿入位置が i + 1 であることに注意する。
21 - 27行目 : 挿入ソートのテストコードである。

実行結果は次の通りで、ソートが行われていることがわかる。

ソート前: False [246 161  55 103 246  39  51 148 205 220]
ソート後: True [ 39  51  55 103 148 161 205 220 246 246]

さて、せっかく前の記事で作成した is_sorted 関数だが、こうテストしてみると別に必要ねーから今回でクビになるかもしれない。

ループ不変式による正当性の証明

ループ不変式というものを使ってアルゴリズムが正しいことを証明する。ループ中でこの不変式が "不変" であればアルゴリズムが正しいというわけである。

不変式によるアルゴリズムの正当性の証明は、数学的帰納法と類似している。数学的帰納法は、

命題がn = 1 のときに真であることを証明する。
命題がn = k のときに真ならn = k + 1のときにも真であることを証明。
命題は正しい。

というやつである。

ところで、アルゴリズムはいつか終了し、正しい答えが得られていなければならない。よって上記に加え、アルゴリズムが終了した時にループ不変式が満たされていることも確認する必要がある。これが数学的帰納法との相違点である。

今回、ループ不変式は次のものである。

上記コードの for ループの各繰り返しが開始されるときには、 A[0 .. j - 1] はソートされた状態となっている。

要は、ループで j が 1 ずつ増分していくに際し、ソートされた要素も1つずつ増えていくということである。

アルゴリズムの正当性を確認するには、次の3つの条件について、ループ不変式が満たされることを証明すればよい。

初期条件 (数学的帰納法1. に相当)
ループ内条件 (数学的帰納法2. に相当)
終了条件

サクッと1つずつ証明していこう。

初期条件

for ループの開始時、つまり j = 1 のときループ不変式が満たされているか確認する。確認すべき部分配列は A[0 .. 0] 、即ち A[0] なのだが、要素が1つしかないのだから、当然この部分配列はソートされており、ループ不変式は満たされているため証明完了である。

ループ内条件

ループが進んでいき、j = k のときループ不変式 (A[0 .. k -1] がソートされていること) が満たされると仮定すると次のループ (j = k + 1 ) のときにもループ不変式 ( A[0 .. k] がソートされていること) が満たされることを証明する。

j = k となったループの開始時、 A[0 .. k - 1] がソートされた状態となっていると仮定する。既に上記で確認したように、A[k] を挿入する位置を見つけ出し挿入するため、A[0 .. k] の要素がソートされていることになる。

次のループで j = k + 1 となったとき、A[0 .. k] がソートされているため、証明完了である。

終了条件

ループでは j は1ずつ増分していく。ループ内の処理が行われるのは j が 1 から (A の長さ - 1) のときまでであるが、さらにj が1だけ増分したときループの条件が満足されなくなり、アルゴリズムは終了する。即ち最後には j は A の長さと等しくなっている。

したがって、A[0 .. A の長さ - 1] がソートされているため、証明完了である。

さて、本書の文意を読み取るとこういう意味かとは思うのだが、若干狐につままれた感じがある。というのは、このループは j は1 から A の長さまで増分していくという意味であって、最終的に j がAの長さと等しくなるということはないのである。

しかしfor ループを while ループに差し替えて、その条件を i < len(A) とし、ループ中で i を1ずつ増分させていくように書き換えれば、上記の意味は通るはずなので深く考えないことにした。