組み込み開発のためのPython · レッスン 161 / 220
挿入ソートを理解する
挿入ソートは整列済み部分へ次の要素を挿入します。小規模またはほぼ整列済みデータでは有用ですが、逆順入力ではO(n²)となります。
挿入ソートは整列済み部分へ次の要素を挿入します。小規模またはほぼ整列済みデータでは有用ですが、逆順入力ではO(n²)となります。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
挿入ソートは整列済み部分へ次の要素を挿入します。小規模またはほぼ整列済みデータでは有用ですが、逆順入力ではO(n²)となります。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
values = [5, 2, 4, 1]
for index in range(1, len(values)):
current = values[index]
position = index
while position and values[position - 1] > current:
values[position] = values[position - 1]
position -= 1
values[position] = current
print(values)手を動かす課題
整列済み・逆順・重複入力で比較回数を数え、標準ソートと比較してください。