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

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

挿入ソートとは？

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

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

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

挿入ソートの計算量

挿入ソートの計算量は「Ｏ（ｎ²）」であり、安定ソートです。

挿入ソートの特徴

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

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を用いて作成した挿入ソートの関数です。

６〜８行目の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]

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

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

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

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

超オススメのPC用品

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

外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／