Pythonのクイックソート
値をピボット未満、同値、超過のグループに分けます。
Pythonのクイックソートとは？
値をピボット未満、同値、超過のグループに分けます。
ピボットを基準に値を分割します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
Pythonのクイックソートのビジュアライザー
O(n log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
main.py
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))期待される出力
[1, 5, 7, 8, 9, 10]仕組み
平均時間O(n log n)ですが、不適切なピボットではO(n²)になります。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。