【初心者向け】Pythonで挿入ソートを実装する方法｜仕組みとコード例をわかりやすく解説

Pythonの挿入ソート（Insertion Sort）は、手札のトランプカードを並べ替える作業によく似ています。挿入ソートでは、「整列済みリスト」と「未整列リスト」の2つの領域を作り、未整列リストの要素を1つずつ取り出しては正しい位置へと挿入していきます。挿入ソートはPythonにおける基本的なアルゴリズムのひとつであり、学習しておく価値のある重要な概念です。

トランプの手札を並べ替えた経験はありませんか？それこそが、Pythonの挿入ソートを理解するための最良のイメージです。要素数の少ないリストを並べ替えたいとき、挿入ソートはとても便利な選択肢になります。

この記事では、挿入ソートとは何か、どのように動作するのかを解説し、具体的なコード例とともにPythonでの実装方法を紹介します。記事を読み終える頃には、このソートアルゴリズムを使いこなせるようになっているはずです。

Pythonの挿入ソートとは？

挿入ソートは、リストを「整列済み部分」と「未整列部分」の2つのサブリストに分割します。そして、未整列部分の各要素を順番に比較しながら、リスト全体が整列するまで処理を繰り返します。

具体的には、未整列部分から1つの要素を取り出し、整列済みサブリストの中の適切な位置へ移動させます。両方のサブリストは同じ配列内に存在しますが、どの要素がすでに整列済みかを区別する役割を持っています。

挿入ソートの動きは、カードゲームで手札を並べ替える様子にたとえると分かりやすいでしょう。

カードを1枚ずつ順番に見ていき、他のカードと比較します。整列済みのカードは左手側に、未整列のカードは右手側に置かれ、すべてのカードが整列するまでこの作業を続けます。

挿入ソートの仕組み

それでは実際に、挿入ソートを使って配列を並べ替えてみましょう。次のような未整列の配列を考えます。

9

4

3

5

挿入ソートでは、最初の要素は「すでに整列済み」とみなします。次に、2番目の要素を専用の変数に格納します。ここではこの変数を current_number（現在の値）と呼びます。

整列済み	current_number
9	4	3	5

次に、current_number を配列の先頭要素と比較します。current_number の方が大きければそのままの位置に留まり、そうでなければ先頭要素の前に移動します。

4は9より小さいので、この2つの要素は入れ替わります。

4

9

3

5

これでリストの最初の2つの要素が整列しました。続いて、current_number の値を3番目の要素に更新し、その左側にあるすべての要素と比較します。

current_number は3になります。以下の比較を行います。

• 3は9より大きいか？ → いいえ。3を9の前に挿入します。
• 3は4より大きいか？ → いいえ。3を4の前に移動します。

リストは次のようになりました。

3

4

9

5

このプロセスを、リスト全体が整列するまで繰り返します。今回のリストは4つの値しかないため、あと1回の比較だけで完了です。次の反復では、5が current_number になります。

• 5は9より大きいか？ → いいえ。5を9の前に移動します。

5は整列済みリストの最後の数字なので、これ以上の比較は不要です。この反復が終わると、配列は完全に整列されます。

3

4

5

9

これだけシンプルです！この挿入ソートでは、常に整列済みの値をリストの左側に保ち、未整列の値を右側に置くという方針で進めました。

リストの各反復ごとに current_number を未整列の項目すべてと比較し、リストが整列するまでこの処理を繰り返したのです。

Pythonで挿入ソートを書く方法

紙の上で挿入ソートの流れを確認するのは簡単ですが、ここからが本番です。実際にPythonで挿入ソートを実装してみましょう。

ソート関数を書く

まず、ソートを行うPython関数を作成します。

def sortNumbers(toSort):
	for number in range(1, len(toSort)):
		current_number = toSort[number]
		i = number - 1

		while i >= 0 and current_number < toSort[i]:
			toSort[i + 1] = toSort[i]
			i -= 1

		toSort[i + 1] = current_number

このコードの仕組みを見ていきましょう。sortNumbers 関数では、Pythonのforループを使ってリスト内のすべての要素を走査します。そして、最初の要素を変数 current_number に代入することで、整列済みの値として扱います。

次に、未整列リスト内のすべての要素（current_number 以降の要素）を反復処理し、current_number を左側の各数値と比較します。比較が完了したら、current_number の値をリスト内の次の要素に更新して同じ処理を繰り返します。

メインプログラムを書く

続いて、挿入ソートを実行するメインプログラムを書きます。

numbers = [9, 4, 3, 5]
sortNumbers(numbers)

print(numbers)

このコードの出力結果は次のとおりです。

[3, 4, 5, 9]

リストが昇順に整列されました！ここまで読み進めたあなた、お見事です。

降順で挿入ソートを行うには

挿入ソートは、数値を降順に並べ替えることもできます。その場合は、whileループ内の「小なり」記号を「大なり」記号に変更するだけです。

while i >= 0 and current_number > toSort[i]:

この1行を先ほどのコードに置き換えることで、リストの要素を逆順（降順）に並べ替えられます。

挿入ソートはどんなときに使うべきか

挿入ソートが最も効果を発揮するのは、リストのデータがほぼ整列済みの場合や、小さなリストを扱う場合です。大きなリストを並べ替える場合には、マージソートやクイックソートなど、より効率的なアルゴリズムの方が高速に動作します。

なお、挿入ソートはバブルソートよりも高速である点も覚えておきましょう。

また、挿入ソートの知識はそれ自体が有用です。挿入ソートの実装方法を身につければ、使えるソートの種類がもうひとつ増えます。

さらに、挿入ソートは他のソートアルゴリズムに比べて構造がシンプルです。挿入ソートをマスターすれば、マージソートなど、より複雑なソートアルゴリズムへの理解もぐっと近づきます。

挿入ソートの計算量分析

すべてのアルゴリズムと同様に、最良・最悪・平均の各計算量を考慮することが重要です。これにより、アルゴリズムがその目的（今回はリストの並べ替え）に対してどれほど効果的かを把握できます。

挿入ソートの最悪計算量と平均計算量は O(n²) です。これは、リストに追加する値が増えるほど、アルゴリズムの処理速度が指数的に遅くなることを意味します。

一方、最良計算量は O(n) です。これは、すでに整列済みのリストに対してアルゴリズムを実行した場合に起こります。アルゴリズムは各要素が整列済みであることを確認すると、すぐに処理を終了します。

アルゴリズムの計算量の表記方法については、ビッグオー記法（Big O Notation）に関する2部構成のシリーズ記事で詳しく学ぶことができます。

まとめ

挿入ソートは、カードゲームで手札を並べ替える作業にたとえられます。整列済みのアイテムのリストと、これから整列すべきアイテムのリストの2つを保持し、未整列リストを順番に処理しながら、すべての要素が整列するまで位置を入れ替えていくのです。

Pythonプログラミングのさらなる学習リソースをお探しですか？「Pythonの学び方」完全ガイドもぜひチェックしてみてください。Pythonの効果的な学習方法のコツや、おすすめのオンライン講座、書籍などのリソース一覧を掲載しています。