クイックソートとマージソート

質問

クイックソートとマージソートではどちらか実用的でしょうか？
教えてください。

回答No.3

rinkun · ベストアンサー

目的によって違う。
単純な速度については一般的にクイックソートはマージソートより2倍程度速いとされている。
ただしクイックソートはマージソートと違って固定的(キー値が同じオブジェクトの順序を変えない)ではないので、複数キーを使って繰り返しソートするような場合には使えないし、ランダムアクセスをするのでメモリ上に入りきらない大きなデータに対するソートには使えない。
またクイックソートは平均的にはn*log(n)速度だが最悪時はn^2オーダーになることがある。
ちなみにJavaのjava.util.Arrays.sortでは基本型に対するものは「調整されたクイックソート」が、オブジェクト型に対するものは「修正マージソート」が使われている。

お礼

どうもありがとうございました。

回答No.2

a-saitoh

どのような用途に使うのかを決めないと、実用的かどうかは決められませんよ。

「一般的に言って」というのは意味無しです。現実にはそれぞれの聴取短所を考えて使い分けられています。そこいらの話はここで聞かなくてもちょっと検索すればすぐに出てくると思いますが。

回答No.1

Tacosan

「実用的」というのを, どのような観点で考えてます?

補足

もうしわけありません。
どちらのほうがより多く計算できるか？
どちらのほうが速く計算できるか？
を出来るだけ詳しく知りたいです。