Pythonのクイックソート(quick sort)
このレッスンでは、基準となる要素(ピボット)のまわりでリストを分けて、クイックソートを実装します。
はじめに
どんな問題を解決するか
クイックソートは、平均的に速く、コードにも書きやすいので、最も広く使われている並べ替えの考え方の1つです。ここでは、問題のもう1つの分け方が分かります。真ん中で分けるのではなく、選んだ値を基準にして分けるのです。
身近なたとえ
クイックソートは、選んだ1冊を基準にして、本を背の高さの順に並べるようなものです。基準より低い本は左の山へ、高い本は右の山へ、同じ高さの本は真ん中に置きます。それから左右の山をそれぞれ同じ方法で並べ、最後に山をつなぎ合わせます。
pivot = values[len(values) // 2]📕 比べる基準の本を1冊選ぶlower = [... if value < pivot]⬅️ 低い本は左へhigher = [... if value > pivot]➡️ 高い本は右へquick_sort(lower) + equal + quick_sort(higher)📚 両側を並べてから山をつなぐクイックソートは、ピボット(基準にする値)を1つ選び、ほかの要素をそれより小さいものと大きいものに分け、それぞれを再帰的に並べ替えてからつなぎます。平均で O(n log n) の時間がかかります。
重要なポイント
if len(values) <= 1:はベースケースです。要素が1つ以下のリストは、すでにソート済みだからです。pivot = values[len(values) // 2]は真ん中の値をピボットにします。lower、equal、higherは、ピボットを基準に値を分けたものです。equalにはピボットと同じ値がまとめて入ります。quick_sort(lower) + equal + quick_sort(higher)で、両側を並べ替えてから3つのリストをつなぎます。
どんな場面で使う?
- 分割(パーティション)と再帰を学ぶ。
- プログラミング言語やライブラリが備える、汎用のインプレースソート(余分なリストを作らない並べ替え)。ただしピボットは慎重に選びます。
- 中央値を求めるなどの選択問題。クイックセレクトも同じ分割を使います。
使わなくてよいとき
- ふだんの Python コード:
sorted()のほうが速く、しかも安定ソートです(等しい値の順番が変わりません)。 - 最悪の場合の速さを保証したい場合:ピボットの選び方が悪いとクイックソートは
O(n²)になりますが、マージソートはそうなりません。
Pythonのクイックソート(quick sort)のビジュアライザー
O(n log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
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]
コードの解説
この読みやすい実装では、真ん中の要素をピボットにし、リスト内包表記でlower、equal、higherの3つのリストを作ります。結果はquick_sort(lower)、equal、quick_sort(higher)をつなげたものです。平均の計算量はO(n log n)ですが、ピボットの選び方が悪いとO(n²)まで遅くなることがあります。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
ピボットと等しい値を取りこぼす
< と > だけで分けると、ピボットと同じ値がほかにあっても消えてしまいます。
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ