クイックソート
値を1つ選び（これをピボットと呼びます）、小さい値をその左へ、大きい値を右へ動かします。そのあと左右それぞれで同じことをします。
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- いいえ
- はい
最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- ピボット
- 位置が確定
試してみましょう: 逆順のリストを選んでください。ピボットがいつも残りの最小値か最大値になるので、分けるたびに片側が空になり、コストが n² に近づきます。
仕組み
ここではピボットを範囲の最後の値にします。左から右へ見ていき、ピボット以下の値を左側へ入れ替えます。最後にピボットを2つのグループの間に置くと、その位置は確定です。左右のグループも同じ方法で並べ替えます。
向いている場面
実際に最も速い並べ替え方法の1つで、追加のメモリもほとんど要りません。ただし悪いピボットばかり選ぶと遅くなります。最初から並んでいるリストがその例です。実際の実装では、ピボットをもっと慎重に選びます。