クイックソートのアルゴリズムについて

質問

(1)クイックソートが使われるのは実際にはどのような場面なのでしょうか？メインメモリで使われていると聞きましたが‥
(2)クイックソートが一番早いと聞きましたがコームソートやバブルソートなどは使われないのでしょうか？
(3)マージソートはどのような局面で使われるのでしょうか？

回答No.8

noname#25358 · ベストアンサー

＃１です。再登場。

>具体的にはどんなデータを扱っているのでしょうか？
　ＳＱＬのエンジンです。フリーで出してるんです。
　どんなデータが来るか予測できないので、ソート方式の選定には苦労した記憶があります。
　ちなみに、自分なりに実験した結果、俺が使ってるｐ－マージソートは、クイックソートと比べても遅延は少ししかないみたいです。

回答No.7

dekopa-

(1) 今ある言語のソート機能は基本的にクイックソートでしょう。プログラマは２つのデータの比較方法だけを定義します。ソートアルゴリズムを１から組む必要は、いまは殆どありません。

(2) 汎用的なソートの中で最速ですから、わざわざ他を使う必要は無いでしょう？そもそも、ライブラリをそのまま使うだけですから選択肢はありませんし。

(3) ソート済みの複数のデータを１つにまとめたい場合です。

回答No.6

don_go

(1)Cでは、qsort()が有るので良く使用します。
＞メインメモリで使われていると聞きましたが‥
ほとんどのソートはメモリ上で行われます。

(2)数十件程度の場合は、バブルソートで済ませる場合
が有ります。
C以外の言語で、数百件から千件程度であれば、データ
領域と別にワークメモリを必要とせず、データの並び方
に影響を受ける事が少なく安定した速度を出せるので
コムソートを良く使用しています

(3)件数が多くメモリに余裕が無い場合に、他のソートと
組み合わせて使用されます。

回答No.5

mydummy

(2)
競馬ゲームをサクッと組んだとき、リアルタイムで順位変動を表示する方法としてバブルソートを使用。
常時更新かつたまに1つだけ順位が入れ替わるだけなので、バブルソートでやるとほぼNで終了します。

回答No.4

rinkun

(1) Cのqsort関数を使う場合に間接的に使いますね。
自分でソートアルゴリズムを書く場合は挿入ソートなどもっと簡単なアルゴリズムでお茶を濁します。
なお、クイックソートのアルゴリズムからすれば、メインメモリ以外のランダムアクセス・コストが大きい媒体上で実施するのは困難だと思います。

(2)平均的にはクイックソートが一番速いです。ただ最悪時は遅いので、これが問題になる場合はマージソートなどを使います。コームソートやバブルソートを実用している例は知りません。小さなソートでも比較ソートか挿入ソートを使いますし。

(3)マージソートが使われるのは2つの局面があります。
一つはメモリに入りきらないデータのソートです。
もう一つは比較キーが同じデータの順序を保存したい場合です。これは複数のキーで順にソートする場合などに必要です。この同一順位のデータ順序を保存する性質をstableと言い、マージソートはstableです。ちなみにJavaのライブラリではソートにstableを要求しており、JREの実装はマージソートを使っています。

回答No.3

okg00

http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/

(1)あらゆる場面で使われていると思います。
(2)交換回数は少ないのですがメモリ消費量が多いので、組込み用途など限られたメモリで処理をする時に他のアルゴリズムが使用されることもあるそうです。まあ、処理時間とデータの配置・件数と空きメモリ、安定ソートの必要性etcとの相談です。件数が極端に少ないとバブルソートの方が早いこともありますし。
(3)もとのデータがほぼ整列済である場合などかなと予想。

お礼

なるほど、データ数によるのですね。

回答No.2

chie65536

(1)
クイックソートを実装したＣ標準ライブラリqsort関数が「要素をメモリ上で入れ換える」と言う実装を行っているので、この標準関数を使う限りはメインメモリ上で行うしかありません。

(2)
要素の比較回数の平均を取ると、クイックソートが断然に比較回数が少なくなります。
但し、ソート前の要素の並びが最悪の場合は、クイックソートの実行速度（比較回数の多さ）はバブルソート並みにまで落ちます。

(3)
ソート済みの複数のファイルを結合する場合に使われます。

例えば、メインメモリが足りず一気にクイックソートするには巨大過ぎるファイルをソートする場合は、メインメモリ上でクイックソートが可能なサイズにファイルを分割し、分割した個々のファイルを別々にクイックソートして複数の中間ファイルに出力します。

それぞれの中間ファイルは個々にソート済みなので、それらを１つの巨大ファイルにソートして書き出す際に、マージソートを使用します。

お礼

ありがとうございます。まず分割して各々をクイックソートしてからマージソートですね。

回答No.1

noname#25358

単純なソートはほとんどクイックソートですね。
　ソートってのは速度が命ですから、遅いソートは、アルゴリズムの勉強をする以外の役にはたちません。
　よって、よほど特別で明確な理由がない限り、個人がプログラムを組むときは、クイックソート以外の手法に手を出すべき局面というのもちょっと思いつきません。
　プロが実務で組むときはビンソートと組み合わせたりしますが。

　ちなみに、よほど特別な理由というのを、俺自身１つだけ過去に持っていたことがあります。
　フリーのデータ管理ソフトを作る際に、「同一であるデータの順序を保障したい」という妙な理由で、ｐ－マージソートという特殊な手法を使っていました。
　これは２次元配列を複数のキーによってソートするときに生じる問題でした。

　今でもそのソフトにはｐ－マージソートが載っていますが、現在では全体処理をもっと速いアルゴリズムに変更していますので、これを使い続ける意味はなくなっています。
　ですが、面倒なんでそのまま使い続けています。
　クイックソートってのは、ネット上にホイホイ落ちてるようなサンプルを使うと、特殊なデータ配列のときにハングアップすることがあって、それを実務に絶えうる形に変更するのが手間だったんです。

お礼

ありがとうございます。スピードを要するデータ管理ではソートのアルゴリズムがかなり重要なのですね。具体的にはどんなデータを扱っているのでしょうか？