スタック・オーバーフロー Asked on November 5, 2021
クイックソートの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とする
↓
以降も最小値を選び続ける
定性的な解釈としては「分割の回数が減って全体の時間計算量も減る」というので合っているはずですが、定量的に確認するには計算量をちゃんと計算する必要があります。通常の計算量解析と同様に計算してみてください。 https://en.wikipedia.org/wiki/Quicksort#Formal_analysis あたりが参考になります。
以下細かい点の指摘です。
Answered by nekketsuuu on November 5, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP