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

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

No.3 ベストアンサー 回答者： rinkun 回答日時： 2007/02/13 14:52

目的によって違う。

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

この回答へのお礼

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

お礼日時：2007/02/14 06:03

No.2 回答者： a-saitoh 回答日時： 2007/02/13 14:47

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

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

No.1 回答者： Tacosan 回答日時： 2007/02/13 13:00

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

この回答への補足

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

補足日時：2007/02/13 13:23