1 歩ずつ動かす
[5, 2, 8, 1, 9, 3, 7, 4] を小さい順に並べる
- 50
- 21
- 82
- 13
- 94
- 35
- 76
- 47
- 比較中
- 入れ替えた
- 位置が決まった
- いま扱う範囲
- 箱の上の字は、基準と、境目の i と、見ている j
- 箱の下の数字は添字
1 歩目 / 全 39 歩比べた回数 0 回入れ替えた回数 0 回
8 個の値を小さい順に並べます。末尾の値を基準にして、基準以下の側と大きい側に分けていきます。
いま動いている疑似コードの行
- 1quick_sort(lo, hi) を次のとおり行う
- 2lo >= hi なら何もしない (1 個は並んでいる)
- 3基準 = a[hi]、i = lo - 1
- 4j を lo から hi - 1 まで 1 つずつ増やす
- 5a[j] <= 基準 なら i を 1 つ進め、a[i] と a[j] を入れ替える
- 6a[i + 1] と a[hi] を入れ替える (基準の添字 p が決まる)
- 7quick_sort(lo, p - 1) と quick_sort(p + 1, hi) を行う
見本を変える
予想してみる
この歩には問題がありません。「1 歩進む」で、次の問題が出るところまで進めましょう。
今回わかること
- 基準の値で、基準以下の側と大きい側に分ける流れ
- 平均では O(n log n) なのに、並んだ入力ではいちばん遅くなる理由
前提
- 配列と添字 (0 から数える番号)
- 再帰 (関数が自分を呼ぶ書き方)
- 2 つの値を入れ替える書き方
どんな並べ方か
クイックソートは、基準になる値を 1 つ選び、基準以下の値を左、基準より大きい値を右に分けてから、左右をそれぞれ同じやり方で並べる並べ方です。分け終えた時点で、基準の位置は最終の位置に決まります。
ここでは、範囲の末尾を基準にして、左から順に基準以下の値を集めていく書き方を使います。基準が真ん中あたりの値になれば半分ずつに分かれて速く、端の値ばかりになると 1 個ずつしか減らず遅くなります。
手順と具体例
- 1範囲の末尾の値を、基準にする
- 2左から順に見て、基準以下の値を左端のほうへ集める
- 3最後に基準を、基準以下の側と大きい側の境目へ入れ替える
- 4基準の位置が決まる
- 5基準の左と右を、それぞれ同じやり方で並べる (1 個になったら終わり)
| 区切り | 比べた / 入れ替えた | 終わったときの並び |
|---|---|---|
| 基準 4 で分ける (添字 0 から 7) | 7 回 / 4 回 | 2, 1, 3, 4, 9, 8, 7, 5 |
| 基準 3 で分ける (添字 0 から 2) | 2 回 / 0 回 | 2, 1, 3, 4, 9, 8, 7, 5 |
| 基準 1 で分ける (添字 0 から 1) | 1 回 / 1 回 | 1, 2, 3, 4, 9, 8, 7, 5 |
| 基準 5 で分ける (添字 4 から 7) | 3 回 / 1 回 | 1, 2, 3, 4, 5, 8, 7, 9 |
| 基準 9 で分ける (添字 5 から 7) | 2 回 / 0 回 | 1, 2, 3, 4, 5, 8, 7, 9 |
| 基準 7 で分ける (添字 5 から 6) | 1 回 / 1 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| いちばん速い | およそ n log₂ n 回 (毎回ほぼ半分に分かれる) | O(n log n) |
| 平均 | およそ 1.39 × n log₂ n 回 | O(n log n) |
| いちばん遅い | n(n - 1) ÷ 2 回 (基準がいつも端の値) | O(n²) |
末尾を基準にすると、もう並んでいる 8 個で 28 回比べる、いちばん遅い形になります。ばらばらの見本では 16 回です。基準を真ん中の値やランダムに選ぶと、この遅い形を避けやすくなります。
使いどころ
向いているとき
- 要素が多く、作業用の列を用意せずに速く並べたいとき
- 平均の速さを重視し、同じ値の順番は気にしないとき
- 基準をランダムに選ぶなど、遅い形を避ける工夫ができるとき
向いていないとき
- 同じ値の順番を崩したくないとき (安定な並べ方ではない)
- どんな入力でも最悪の時間を抑えたいとき (マージソートを使う)
コード
疑似コード
- 1quick_sort(lo, hi) を次のとおり行う
- 2lo >= hi なら何もしない (1 個は並んでいる)
- 3基準 = a[hi]、i = lo - 1
- 4j を lo から hi - 1 まで 1 つずつ増やす
- 5a[j] <= 基準 なら i を 1 つ進め、a[i] と a[j] を入れ替える
- 6a[i + 1] と a[hi] を入れ替える (基準の添字 p が決まる)
- 7quick_sort(lo, p - 1) と quick_sort(p + 1, hi) を行う
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- もう並んでいる配列が、なぜいちばん遅いのですか？
- 末尾が最大の値なので、基準以下の側に残り全部が入り、大きい側は空になるからです。範囲が 1 個ずつしか減らず、n 回の分け直しで n(n - 1) ÷ 2 回比べます。
- 基準は、末尾の値でないといけませんか？
- いいえ。真ん中の値や、ランダムに選んだ値でも並べられます。その値を末尾と入れ替えてから同じ手順を使えば、並んだ入力でも遅くなりにくくなります。
- クイックソートは、なぜ安定な並べ方ではないのですか？
- 基準以下の値を左へ集めるときに、離れた値どうしを入れ替えるからです。同じ値の順番が前後することがあります。
