Pythonの挿入ソート(insertion sort)
このレッスンでは、各要素を整列済み部分の正しい位置に差し込んでいく挿入ソートを実装します。
はじめに
どんな問題を解決するか
データは、ほぼソート済みの状態で届いたり、1つずつ届いたりすることがよくあります。たとえば、ソート済みの点数の一覧に新しい点数が1つ加わる場合です。そのたびに全部を並べ替え直すのは無駄です。挿入ソートはこういう場面がとても得意で、多くの人がトランプの手札を並べるときのやり方でもあります。
身近なたとえ
挿入ソートは、トランプの手札を並べるときのやり方です。カードを1枚ずつ取り、それより大きいカードを飛び越えて左へ動かし、正しい位置に差し込みます。そのカードより左側は、いつも順番どおりに並んでいます。
current = result[index]🃏 次のカードを取るresult[position] > current👈 左のカードのほうが大きい?result[position + 1] = result[position]➡️ 大きいカードを1つ右へずらすresult[position + 1] = current📥 空いた所にカードを置く挿入ソートは、大きい要素を右へずらし、空いた所に今の要素を差し込むことで、ソート済みの部分を1つずつ広げていきます。最悪の場合は O(n²) ですが、ほぼソート済みのデータでは O(n) に近くなります。
重要なポイント
for index in range(1, len(result)):は2番目の要素から始めます。要素が1つだけなら、すでにソート済みだからです。currentは、大きい値をずらしている間、これから差し込む値を覚えておきます。while position >= 0 and result[position] > current:は大きい値を1つずつ右へずらします。result[position + 1] = currentで、空いた所に値を置きます。
どんな場面で使う?
- 小さい、またはほぼソート済みのリスト。
- 新しい要素が届くたびにリストを並べ替えたまま保つ。
- 高速な並べ替えの仕上げ。高速なアルゴリズムも、小さく分けた部分には挿入ソートに切り替えて使います。
使わなくてよいとき
- 順番がばらばらの大きなリスト:要素をずらす作業に時間がかかるので、
sorted()を使います。 - 大きなソート済みリストに何度も挿入する場合:
bisect.insortなら二分探索で挿入位置を見つけてくれます。
Pythonの挿入ソート(insertion sort)のビジュアライザー
O(n²)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
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つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
ループの中で 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 のレビューも受けられます。
すべてのチャレンジ