シェルソート，クイックソート

質問

シェルソートは比較数が小さいとクイックソートよりも早いですが，なぜでしょうか？

回答No.2

BLUEPIXY · ベストアンサー

一概には言えないかもしれませんが、
一般的には、手順が難しくなるほど
要素数が少ない場合にはその手順に要する時間の割合がバカにならないので比較的遅くなる傾向があります。（逆に要素数が大きい場合には、手順（アルゴリズム）に要する時間より効果が大きくなります。

おおざっぱにいって、
シェルソートとクイックソートが要素数が小さい時に差が大きめに出るとすると、関数の（再帰）呼び出しの部分で時間が取られているのではないかと思います。
実際の場面ではプロファイラーとかを使わないと、どこでより多くの時間を消費しているかとかの分析はできません。
また、クイックソートは、要素の並びによっては非常に効率が悪くなるので（こういう検討をするには）要素の並びがランダムになっている必要があります。

比較数というのを要素数だと理解して回答してみましたが、勘違いしてたらすみません。

お礼

その通りです、比較数＝要素数ということでした。
ありがとうございます。

回答No.1

notnot

ロジックが簡単だからですね。
ソートの速度はよくデータ個数(N)の何乗に比例するとかで比較されます。クイックソートはNlogNに比例、シェルソートはNの1.2～2乗に比例なんで、Nが非常に大きいとクイックソートが早いですが、同じ比例するといってもそれぞれ比例係数が違います。Nが小さいとロジックが簡単で比例係数が小さいソートのほうが早いです。

携帯電話の料金で、どれくらい電話を使うかによって最適な料金プランが人によって異なるのと同じです。ほとんど電話を使わないなら、単純に基本料金が安いものがよい。

お礼

ありがとうございます。