pythonでソートアルゴリズム -挿入ソート

はじめに

プログラミング初心者がソートアルゴリズムを自分なりに理解し、コーディングしてみたものの忘備録になります。
間違いもあるかもしれませんがご了承ください＆ご指摘いただけると助かります…。
ここでは挿入ソートを扱います。
参考にした本と記事はこちら
→https://www.codereading.com/algo_and_ds/algo/
→https://book.impress.co.jp/books/1118101057

挿入ソート

元ある配列の頭から、新しい配列に並び替えつつ挿入していくソートアルゴリズム。
全比較を行うバブルソートや選択ソートと違い、挿入できる箇所を見つければそこで終了するので、比較回数の平均値が少なくなります。

手順

比較回数

最大値

1+2+...+(n-1) = \sum_{k=1}^{n-1} k = \frac{1}{2}n(n-1) 

プログラム

insertion_sort.py

a = [4,6,1,2,3,8,5]

# 1番最初の値は挿入済みとし、0ではなく1から始める
for i in range(1, len(a)):
    # 挿入したい値がすでにa[i]に入っているという感覚でスタート
    for j in range(i, 0, -1):
        # 挿入個所の手前にある数字が挿入した数字より小さい場合
        if a[j] < a[j-1]:
            # 値をひっくり返して配列の頭のほうに攻めていく
            a[j-1], a[j] = a[j], a[j-1]
        # ひっくり返す必要がなくなった時点で、for文を抜け出す
        else:
            break
print(a)

計算量

for文を2重に回すので、O(n^2)となるが、前述のとおり同じ計算量のバブルソートや選択ソートより効率がよくなる。

おわりに

手順は描くよりつくったほうが早くてきれいでいいですね。
ソートは手を動かして書いたほうが理解がしやすくて良いです。
シェルソート、クイックソート、ヒープソート、マージソートについては書きたいです…。