Pythonの挿入ソート
手札を順番に並べる操作に似ています。
Pythonの挿入ソートとは？
手札を順番に並べる操作に似ています。
各要素を整列済み部分の適切な位置へ挿入します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
Pythonの挿入ソートのビジュアライザー
再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
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]仕組み
大きい値を右へずらして挿入位置を作り、ほぼ整列済みのデータでは効率的です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。