エンジニア実践的基礎: 挿入ソート

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

挿入ソートとは

今回から初めてソートを扱います。ソートは並び替えのアルゴリズムです。学校で背の高い順や小さい順に並びましたよね。それがまさしくソートアルゴリズムです。

現実世界では適当に並び変わりますが、コンピュータの世界では厳密な手続きに従います。手続きごとに名前が付いていて挿入ソートは代表的なソートアルゴリズムの一つです。

挿入ソートは「トランプの手札の並び替え」です。ブラックジャックでもポーカーでも何でもいいですが、トランプで遊ぶときに、手札を小さい順や大きい順に揃えた経験はありませんか？その際、おそらく次のような手順を踏むでしょう:

1. 移動するカードを決める

2. 左側のカードが移動カードより大きければ、位置を入れ替える

3. 移動カードより小さいカードが左側にくるまで手順2を繰り返す

この手順を全てのカードに繰り返せば、手札は小さい順になります。これが挿入ソートです。難しい名前がついてますが、トランプのカードを並び替えるだけと考えれば簡単です。

以下、２・３・４・１・6の手札を持つケースのサンプルです。

実装

def insertionSort(arr):
    # 全てのカードを順に調べる
    for i in range(1, len(arr)):
        j = i - 1
　　　　　　　　　　　　　　　　# 対象カードを左のカードと順に比較しながら入れ替える
        while j >= 0 and arr[j + 1] < arr[j]:
            tmp = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = tmp
            j -= 1
    return arr

計算量

ここから新しい計算量の「空間計算量」使います。今までの計算量は「時間計算量」と呼ばれ、非常に大きな入力に対するアルゴリズムの効率性を測定します。それに対し「空間計算量」はアルゴリズムが消費するメモリの量を測定します。

挿入ソートの時間計算量は O(n^2) です。大きい順に並ぶ手札を小さい順にするには、全てのカードを移動する必要があります。正確ではないですが、ざっくりイメージは n 枚のカードが約 n 枚分左に移動すると考えるとわかりやすいです。(厳密な数学の計算はありますが、この理解で実務で問題になることはないでしょう)

空間計算量は O(n) です。初めに与えられたカードの枚数以上に消費することはないからです。

まとめ

最初のソートアルゴリズムを学びました。今後もいくつかソートアルゴリズムを学習しますが、いずれも実生活の経験に例えれば非常にシンプルな手順です。