組み込み開発のためのPython · レッスン 159 / 220
バブルソートを理解する
バブルソートは隣り合う要素を比較して交換する方法です。平均・最悪時O(n²)で、大規模データには標準のsortedを使うのが一般的です。
バブルソートは隣り合う要素を比較して交換する方法です。平均・最悪時O(n²)で、大規模データには標準のsortedを使うのが一般的です。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
バブルソートは隣り合う要素を比較して交換する方法です。平均・最悪時O(n²)で、大規模データには標準のsortedを使うのが一般的です。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
def bubble_sort(values):
result = values[:]
for end in range(len(result) - 1, 0, -1):
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
return result
print(bubble_sort([3, 1, 2]))手を動かす課題
空・一要素・重複を含む入力を試し、元のリストが変更されないことを確認してください。