- ベストアンサー
クイックソートとマージソート
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
目的によって違う。 単純な速度については一般的にクイックソートはマージソートより2倍程度速いとされている。 ただしクイックソートはマージソートと違って固定的(キー値が同じオブジェクトの順序を変えない)ではないので、複数キーを使って繰り返しソートするような場合には使えないし、ランダムアクセスをするのでメモリ上に入りきらない大きなデータに対するソートには使えない。 またクイックソートは平均的にはn*log(n)速度だが最悪時はn^2オーダーになることがある。 ちなみにJavaのjava.util.Arrays.sortでは基本型に対するものは「調整されたクイックソート」が、オブジェクト型に対するものは「修正マージソート」が使われている。
その他の回答 (2)
- a-saitoh
- ベストアンサー率30% (524/1722)
どのような用途に使うのかを決めないと、実用的かどうかは決められませんよ。 「一般的に言って」というのは意味無しです。現実にはそれぞれの聴取短所を考えて使い分けられています。そこいらの話はここで聞かなくてもちょっと検索すればすぐに出てくると思いますが。
- Tacosan
- ベストアンサー率23% (3656/15482)
「実用的」というのを, どのような観点で考えてます?
補足
もうしわけありません。 どちらのほうがより多く計算できるか？ どちらのほうが速く計算できるか？ を出来るだけ詳しく知りたいです。
関連するQ&A
- アルゴリズムの問題なのですが、マージソートとクイックソートについて教え
アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。 数列の(21 99 38 22 15 6)をマージソートで並び変えて、クイックソートでも並び変えたいのです。 マージソートで並び変えた手順は (21 99 38 22 15 6) (下矢印) (21 99 38)(22 15 6) (下矢印) (21 99)(38)(22 15)(6) (下矢印) (21)(99)(38)(22)(15)(6) (下矢印) (21 99)(38)(15 22)(6) (下矢印) (21 38 99)(6 15 22) (下矢印) (6 15 21 22 38 99) となりました。 この時、分割回数と統合回数がともに5なのですが、どう見たら5回なのでしょうか。 分割回数は3で統合回数も3ではないのでしょうか？ クイックソートの方なのですが、 回答は (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22 38)(99) (15と38にした場合) (下矢印) (6)(15)(21)(22)(38)(99) となっていて、 最も効率のよいピボットを選択した場合分割回数は3となっています。 私がやってみたところ (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22)(38)(99) (15と38を選んだ) これではいけないのでしょうか。 長くなりましたが、よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- クイックソートのアルゴリズムについて
(1)クイックソートが使われるのは実際にはどのような場面なのでしょうか？メインメモリで使われていると聞きましたが‥ (2)クイックソートが一番早いと聞きましたがコームソートやバブルソートなどは使われないのでしょうか？ (3)マージソートはどのような局面で使われるのでしょうか？
- ベストアンサー
- C・C++・C#
- 挿入ソートとマージソート
挿入ソートとマージソートの問題を解いているのですが、 途中で行き詰ってしまいました。 （問題文） サイズnの入力に対して、挿入ソートの実行には8n~2ステップかかり、 マージソートの実行には64nlnnステップかかる。 挿入ソートがマージソートに勝るnの値を求めよ。 補足：ln=eを底とするlog （挿入ソートがマージソートに勝る＝挿入ソートがマージソートより実行時間が早い） 8n~2 <= 64nlnn 8lnn=n e~n=n~8 こういう感じで自分なりに考えてみたのですが、nの値をどのように出して良いのかわからず困っています。 どなたかご教授いただける方いましたらよろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- クイックソートって？？
どこに載せればいいのかわからなかったので ここに載せてみました。 クイックソートってなんですか？？ 簡単なアルゴリズムで答えてください！？ （自分も何言っているのかわらない？？） 簡単に言えばクイックソートってナに？？ です。 よろしくお願いします。 わかるように簡単でね！！
- ベストアンサー
- その他（プログラミング・開発）
- 非再帰のマージソートについて
非再帰のマージソートを作成しているのですが、 上手いこと出来なくて困っています。 条件として配列の開始と終了のインデックスを指定して、 その間の要素だけをソートしたいのです。 ex： int array[10] = { 9,8,7,6,5,4,3,2,1,0 }; MergeSort( array, 2, 6 ); // array[2]～array[6]をソート for( int i=0; i<10; i++ ) printf( "%d, ", array[i] ); 出力） 9, 8, 3, 4, 5, 6, 7, 2, 1, 0, 以下のサイトで公開されているマージソートを元に 私なりに弄ってはいるのですが、 メモリを壊してしまうようなエラーが頻発して、 どうもうまくいかないのです・・・。 http://besky-works.spaces.live.com/Blog/cns!555CF2E2F9E31C71!557.entry どなたがおわかりの方がいらっしゃれば、 その方法を教えていただければ助かります。
- ベストアンサー
- C・C++・C#
- Lispでマージソート
Lisp初心者のものです。 Lispでマージソートはどのように書けばいいのでしょうか？ 結果のリストは、二つの引数リストの要素すべてを含んでいなければならず、たとえば (marge ' (3 3 6 7) ' (2 5 8)) の答えは (2 3 3 5 6 7 8) です。
- ベストアンサー
- その他（プログラミング・開発）
- クイックソートでソート数が１個や２個でも正しくソートできるのでしょうか？
使用上意味がないのですが、クイックソートでソート数が１個や２個でも正しくソートできるのでしょうか？ 引数に quick_sort( a[], 0, n - 1 )と、n-1となっているために nは0は無理そうですが、n=1なら0でうまくいくかなと思うのですが、 原理上、どうなっているのでしょうか？ 詳しい方教えて下さい。 http://www.daccho-it.com/program/algo/quick.c
- 締切済み
- 数学・算数
- マージソートについて
マージソートの要素の比較と交換回数を計測するプログラムを作っているのですが、マージのどの段階が交換処理になるのかが分からず困っています。 マージ処理の実行回数をカウントする配列ｓを設けて処理をカウントする場合、以下のプログラムだとどのタイミングでカウントすればよいでしょうか？ ちなみに配列aは初めに値を割り振った配列で、配列bは別途で用意した作業用配列です。 最後のfor文やif文付近で配列の値を変化させて計測してみたのですが、計算量に合った動きをしてくれませんorz void merge_sort(int a[], int low, int high){ int mid, i, j, k; if(low >= high) return; mid = (low + high)/2; merge_sort(a, low, mid); merge_sort(a, mid+1, high); for(i = low; i <= mid; i++) b[i] = a[i]; for(i = mid+1, j=high; i <= high; i++, j--) b[i] = a[j]; i = low; j = high; for(k = low; k <= high; k++){ if(b[i] <= b[j]){ a[k] = b [i++]; } else{ a[k] = b[j--]; } } }
- ベストアンサー
- C・C++・C#
お礼
どうもありがとうございました。