はじめに
プログラミング初心者がソートアルゴリズムを自分なりに理解し、コーディングしてみたものの忘備録になります。
間違いもあるかもしれませんがご了承ください&ご指摘いただけると助かります…。
ここでは挿入ソートを扱います。
参考にした本と記事はこちら
→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)**となるが、前述のとおり同じ計算量のバブルソートや選択ソートより効率がよくなる。
おわりに
手順は描くよりつくったほうが早くてきれいでいいですね。
ソートは手を動かして書いたほうが理解がしやすくて良いです。
シェルソート、クイックソート、ヒープソート、マージソートについては書きたいです…。