概要
概要
基準値の決め方
基準値はどう決めるのか
基準値は、配列の中から『これを目印に左右へ分けよう』と決める値です。
正しい基準値が 1 つだけあるわけではありません。左端、右端、真ん中あたりなど、どれを選んでも動きます。
ここでは、動きを追いやすいように『右端の値を基準値にする』形で見せます。
ただし、いつも端の値ばかり選ぶと、分かれ方が偏って遅くなることがあります。
左端、右端、真ん中あたりから選ぶ
右端を基準値にして動きを確認する
選び方が偏ると遅くなりやすい
ソート / Quick Sort（クイックソート）
1 つ基準値を決めて、それより小さいグループと大きいグループに分けながら進める方法です。基準値の選び方に偏りが出ると遅くなります。
目次
このページでわかること
概要
基準値の決め方
基準値は、配列の中から『これを目印に左右へ分けよう』と決める値です。
正しい基準値が 1 つだけあるわけではありません。左端、右端、真ん中あたりなど、どれを選んでも動きます。
ここでは、動きを追いやすいように『右端の値を基準値にする』形で見せます。
ただし、いつも端の値ばかり選ぶと、分かれ方が偏って遅くなることがあります。
左端、右端、真ん中あたりから選ぶ
右端を基準値にして動きを確認する
選び方が偏ると遅くなりやすい
考え方
基準値を 1 つ決める
基準値より小さいものを左へ集める
基準値より大きいものを右へ集める
左右を同じように整列する要点
O(n log n)
O(n log n)
O(n²)
いいえ
補足
左右がある程度バランスよく分かれると、段数が log n 程度に収まるからです。
毎回かなり偏って分かれると二次時間になります。
基準値を決めて左右へ分ける動きが理解の中心です。
動きで確認
ここでは「基準値がどれか」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。