Pythonアルゴリズム

Pythonのクイックソート(quick sort)

このレッスンでは、基準となる要素(ピボット)のまわりでリストを分けて、クイックソートを実装します。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

クイックソートは、平均的に速く、コードにも書きやすいので、最も広く使われている並べ替えの考え方の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) の時間がかかります。

重要なポイント

  1. if len(values) <= 1: はベースケースです。要素が1つ以下のリストは、すでにソート済みだからです。
  2. pivot = values[len(values) // 2] は真ん中の値をピボットにします。
  3. lower、equal、higher は、ピボットを基準に値を分けたものです。equal にはピボットと同じ値がまとめて入ります。
  4. quick_sort(lower) + equal + quick_sort(higher) で、両側を並べ替えてから3つのリストをつなぎます。

どんな場面で使う?

  • 分割(パーティション)と再帰を学ぶ。
  • プログラミング言語やライブラリが備える、汎用のインプレースソート(余分なリストを作らない並べ替え)。ただしピボットは慎重に選びます。
  • 中央値を求めるなどの選択問題。クイックセレクトも同じ分割を使います。

使わなくてよいとき

  • ふだんの Python コード:sorted() のほうが速く、しかも安定ソートです(等しい値の順番が変わりません)。
  • 最悪の場合の速さを保証したい場合:ピボットの選び方が悪いとクイックソートは O(n²) になりますが、マージソートはそうなりません。

Pythonのクイックソート(quick sort)のビジュアライザー

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]

コードの解説

この読みやすい実装では、真ん中の要素をピボットにし、リスト内包表記でlower、equal、higherの3つのリストを作ります。結果はquick_sort(lower)、equal、quick_sort(higher)をつなげたものです。平均の計算量はO(n log n)ですが、ピボットの選び方が悪いとO(n²)まで遅くなることがあります。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

ピボットと等しい値を取りこぼす

< と > だけで分けると、ピボットと同じ値がほかにあっても消えてしまいます。

問題
return quick_sort(lower) + [pivot] + quick_sort(higher)
修正
return quick_sort(lower) + equal + quick_sort(higher)

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ