> udemyで学習する

挿入ソートとは?【アルゴリズム紹介・Pythonによる実行】

本記事はPythonの挿入ソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要な挿入ソートを一緒に学習しましょう。

挿入ソートとは?

挿入ソートは、非常に有名なアルゴリズムで、そのシンプルなアルゴリズムからよく利用され、整列アルゴリズムを学ぶ上で非常に重要なアルゴリズムです。
下の3ステップで挿入ソートを実現します。

1.0番目と1番目の要素を比較し、順序が逆であれば入れ換える。
2.2番目の要素について、0番目・1番目の順に比較し、順序が整うように適切な位置へ挿入する
3.3番目以降の要素も同様にして、整列済みデータとの比較と挿入を繰り返す。

詳しくは下の動画で理解してください。


挿入ソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n2O(n2O(n)

挿入ソートの計算量は「O(n2)」であり、安定ソートです。

挿入ソートの特徴

挿入ソートは既に整列されている部分が多ければ多いほど、処理が少なくて済むため、処理速度は向上します。故に、昇順を降順に並べ替える場合などのすべての要素をソートする必要がある場合、処理速度は非常に低下します。

Pythonコード

def insertion_sort(nums):
    for i in range(1, len(nums)):
        tmp = nums[i]
        j = i - 1

        while j >= 0 and nums[j] > tmp:
            nums[j + 1] = nums[j]
            j -= 1

        nums[j + 1] = tmp

    return nums

上記がPythonを用いて作成した挿入ソートの関数です。

6〜8行目のwhile文では、挿入が行われる際、要素を一つづつずらしています。
挿入ソートはコードを頭で理解することが少し複雑かと思うので、デバッカーを使ってゆっくりと理解するのがいいと思います。

挿入ソートの実行例

上記で作成した関数を使用して、実際に挿入ソートをPython環境で実行してみました。
下記がそのコードと実行結果です。

def insertion_sort(nums):
    for i in range(1, len(nums)):
        tmp = nums[i]
        j = i - 1

        while j >= 0 and nums[j] > tmp:
            nums[j + 1] = nums[j]
            j -= 1

        nums[j + 1] = tmp

    return nums


if __name__ == '__main__':
    nums = [45, 61, 3, 34, 82, 41, 99]
    print(insertion_sort(nums))
【実行結果】
[3, 34, 41, 45, 61, 82, 99]

実行結果から、
16行目で宣言した[45, 61, 3, 34, 82, 41, 99]のリストを昇順に上手くソートできていることがわかります。

挿入ソートの理解が曖昧な方へ

下の動画も挿入ソートについて、処理速度をイメージすることができます。
繰り返し見てみてくださいね。


ということで、本記事は挿入ソートについて、Pythonのコードを使用しながらまとめました。
最後まで読んでいただき、ありがとうございました\(^o^)/

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです!
僕も感動したこのマウスを、騙されたと思って使ってみてください!(^^)

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です