Pythonアルゴリズム

Pythonの挿入ソート(insertion sort)

このレッスンでは、各要素を整列済み部分の正しい位置に差し込んでいく挿入ソートを実装します。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

データは、ほぼソート済みの状態で届いたり、1つずつ届いたりすることがよくあります。たとえば、ソート済みの点数の一覧に新しい点数が1つ加わる場合です。そのたびに全部を並べ替え直すのは無駄です。挿入ソートはこういう場面がとても得意で、多くの人がトランプの手札を並べるときのやり方でもあります。

身近なたとえ

挿入ソートは、トランプの手札を並べるときのやり方です。カードを1枚ずつ取り、それより大きいカードを飛び越えて左へ動かし、正しい位置に差し込みます。そのカードより左側は、いつも順番どおりに並んでいます。

トランプの並べ方からコードへ
current = result[index]🃏 次のカードを取る
result[position] > current👈 左のカードのほうが大きい?
result[position + 1] = result[position]➡️ 大きいカードを1つ右へずらす
result[position + 1] = current📥 空いた所にカードを置く
左側はいつもソート済みで、新しい要素をそこへ差し込んでいきます。
ひと言でいうと

挿入ソートは、大きい要素を右へずらし、空いた所に今の要素を差し込むことで、ソート済みの部分を1つずつ広げていきます。最悪の場合は O(n²) ですが、ほぼソート済みのデータでは O(n) に近くなります。

重要なポイント

  1. for index in range(1, len(result)): は2番目の要素から始めます。要素が1つだけなら、すでにソート済みだからです。
  2. current は、大きい値をずらしている間、これから差し込む値を覚えておきます。
  3. while position >= 0 and result[position] > current: は大きい値を1つずつ右へずらします。
  4. result[position + 1] = current で、空いた所に値を置きます。

どんな場面で使う?

  • 小さい、またはほぼソート済みのリスト。
  • 新しい要素が届くたびにリストを並べ替えたまま保つ。
  • 高速な並べ替えの仕上げ。高速なアルゴリズムも、小さく分けた部分には挿入ソートに切り替えて使います。

使わなくてよいとき

  • 順番がばらばらの大きなリスト:要素をずらす作業に時間がかかるので、sorted() を使います。
  • 大きなソート済みリストに何度も挿入する場合:bisect.insort なら二分探索で挿入位置を見つけてくれます。

Pythonの挿入ソート(insertion sort)のビジュアライザー

O(n²)

再生またはステップを使って、比較とデータ移動を順に確認できます。

サンプルコード

コードを実行 →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
この例の実行ボタンを作成

実行結果

[1, 3, 4, 5, 9]

コードの解説

変数currentは、これから差し込む値を保持します。whileループはcurrentより大きい値を1つずつ右へずらして空きを作り、そこにcurrentを置きます。最悪の計算量はO(n²)ですが、ほぼ並んでいるデータならO(n)に近くなります。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

ループの中で current を書き戻す

値を置くのは、大きい値をすべてずらし終えたあとの1回だけです。

問題
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
修正
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ