TransWikia.com

クイックソートのpivotが中央値が最も良いとされる理由

スタック・オーバーフロー 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とする
     ↓
以降も最小値を選び続ける

One Answer

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

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

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

Answered by nekketsuuu on November 5, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP