組み込み開発のためのPython · レッスン 162 / 220
クイックソートを理解する
クイックソートは基準値で配列を分割する分割統治法です。平均O(n log n)ですが、基準選択によって最悪O(n²)となり、再帰深度にも注意が必要です。
クイックソートは基準値で配列を分割する分割統治法です。平均O(n log n)ですが、基準選択によって最悪O(n²)となり、再帰深度にも注意が必要です。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
クイックソートは基準値で配列を分割する分割統治法です。平均O(n log n)ですが、基準選択によって最悪O(n²)となり、再帰深度にも注意が必要です。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
def quick_sort(values):
if len(values) < 2:
return values
pivot = values[len(values) // 2]
lower = [x for x in values if x < pivot]
equal = [x for x in values if x == pivot]
upper = [x for x in values if x > pivot]
return quick_sort(lower) + equal + quick_sort(upper)
print(quick_sort([4, 1, 4, 2]))手を動かす課題
重複値を含む入力と既に整列した入力を測定し、教育用実装のメモリコストも確認してください。