クイックソートのpivotが中央値が最もいいとされる理由の認識は下記の通りであっていますでしょうか
以下のような配列があった場合、下のようにpivotに中央値を選び均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
よって中央値で分割できると高速で処理できる。
[4,3,2,5,7,6,9,10,8]
↓基準値を6とする
[4,3,2,5][確定:6][7,8,9,10] ///[4,3,2,5]をグループA,[7,8,9,10]をグループBとします
以降それぞれで処理
反対に最小値や最大値をpivotとして選んだ場合、上記の例のように中央値で分割できていないためグループに大きな偏りが生じる。グループCの場合、分割によって比較回数や交換回数をあまり減らすことができていない。
つまり処理が遅くなってします。
[4,3,2,5,7,6,9,10,8]
↓基準値を2とする
[確定:2][4,3,5,6,7,8,9,10] ///[4,3,5,6,7,8,9,10] をグループCとする
↓
以降も最小値を選び続ける