

クイックソートの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とする  
↓  
以降も最小値を選び続ける


CC BY-SA 4.0
2020-07-21T11:43:13.587
68792
2020-07-26T07:35:19.120
41140
question
アルゴリズム
クイックソートのpivotが中央値が最も良いとされる理由


定性的な解釈としては「分割の回数が減って全体の時間計算量も減る」というので合っているはずですが、定量的に確認するには計算量をちゃんと計算する必要があります。通常の計算量解析と同様に計算してみてください。
<https://en.wikipedia.org/wiki/Quicksort#Formal_analysis> あたりが参考になります。

以下細かい点の指摘です。

  * 「Bの要素は無視してAの中の要素とだけ比較すればよい」というのはクイックソートであればいつでも成り立つ性質です。
  * 「以降も最小値を選び続ける」というのは無限ループしてしまう、クイックソートとしては誤ったアルゴリズムの場合の説明をしてしまっていそうです。


CC BY-SA 4.0
2020-07-26T07:35:19.120
68979
2020-07-26T07:35:19.120
19110
68792
answer