1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

はじめに

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

挿入ソート

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

手順

各ソート.jpg

比較回数

最大値

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)**となるが、前述のとおり同じ計算量のバブルソートや選択ソートより効率がよくなる。

おわりに

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

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?