- ベストアンサー
クイックソートのアルゴリズムについて
- みんなの回答 （8）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
＃１です。再登場。 >具体的にはどんなデータを扱っているのでしょうか？ ＳＱＬのエンジンです。フリーで出してるんです。 どんなデータが来るか予測できないので、ソート方式の選定には苦労した記憶があります。 ちなみに、自分なりに実験した結果、俺が使ってるｐ－マージソートは、クイックソートと比べても遅延は少ししかないみたいです。
その他の回答 (7)
- dekopa-
- ベストアンサー率42% (161/378)
(1) 今ある言語のソート機能は基本的にクイックソートでしょう。プログラマは２つのデータの比較方法だけを定義します。ソートアルゴリズムを１から組む必要は、いまは殆どありません。 (2) 汎用的なソートの中で最速ですから、わざわざ他を使う必要は無いでしょう？そもそも、ライブラリをそのまま使うだけですから選択肢はありませんし。 (3) ソート済みの複数のデータを１つにまとめたい場合です。
- don_go
- ベストアンサー率31% (336/1059)
(1)Cでは、qsort()が有るので良く使用します。 ＞メインメモリで使われていると聞きましたが‥ ほとんどのソートはメモリ上で行われます。 (2)数十件程度の場合は、バブルソートで済ませる場合 が有ります。 C以外の言語で、数百件から千件程度であれば、データ 領域と別にワークメモリを必要とせず、データの並び方 に影響を受ける事が少なく安定した速度を出せるので コムソートを良く使用しています (3)件数が多くメモリに余裕が無い場合に、他のソートと 組み合わせて使用されます。
- mydummy
- ベストアンサー率59% (55/92)
(2) 競馬ゲームをサクッと組んだとき、リアルタイムで順位変動を表示する方法としてバブルソートを使用。 常時更新かつたまに1つだけ順位が入れ替わるだけなので、バブルソートでやるとほぼNで終了します。
- rinkun
- ベストアンサー率44% (706/1571)
(1) Cのqsort関数を使う場合に間接的に使いますね。 自分でソートアルゴリズムを書く場合は挿入ソートなどもっと簡単なアルゴリズムでお茶を濁します。 なお、クイックソートのアルゴリズムからすれば、メインメモリ以外のランダムアクセス・コストが大きい媒体上で実施するのは困難だと思います。 (2)平均的にはクイックソートが一番速いです。ただ最悪時は遅いので、これが問題になる場合はマージソートなどを使います。コームソートやバブルソートを実用している例は知りません。小さなソートでも比較ソートか挿入ソートを使いますし。 (3)マージソートが使われるのは2つの局面があります。 一つはメモリに入りきらないデータのソートです。 もう一つは比較キーが同じデータの順序を保存したい場合です。これは複数のキーで順にソートする場合などに必要です。この同一順位のデータ順序を保存する性質をstableと言い、マージソートはstableです。ちなみにJavaのライブラリではソートにstableを要求しており、JREの実装はマージソートを使っています。
- okg00
- ベストアンサー率39% (1322/3338)
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/ (1)あらゆる場面で使われていると思います。 (2)交換回数は少ないのですがメモリ消費量が多いので、組込み用途など限られたメモリで処理をする時に他のアルゴリズムが使用されることもあるそうです。まあ、処理時間とデータの配置・件数と空きメモリ、安定ソートの必要性etcとの相談です。件数が極端に少ないとバブルソートの方が早いこともありますし。 (3)もとのデータがほぼ整列済である場合などかなと予想。
- chie65536
- ベストアンサー率41% (2512/6032)
(1) クイックソートを実装したＣ標準ライブラリqsort関数が「要素をメモリ上で入れ換える」と言う実装を行っているので、この標準関数を使う限りはメインメモリ上で行うしかありません。 (2) 要素の比較回数の平均を取ると、クイックソートが断然に比較回数が少なくなります。 但し、ソート前の要素の並びが最悪の場合は、クイックソートの実行速度（比較回数の多さ）はバブルソート並みにまで落ちます。 (3) ソート済みの複数のファイルを結合する場合に使われます。 例えば、メインメモリが足りず一気にクイックソートするには巨大過ぎるファイルをソートする場合は、メインメモリ上でクイックソートが可能なサイズにファイルを分割し、分割した個々のファイルを別々にクイックソートして複数の中間ファイルに出力します。 それぞれの中間ファイルは個々にソート済みなので、それらを１つの巨大ファイルにソートして書き出す際に、マージソートを使用します。
お礼
ありがとうございます。まず分割して各々をクイックソートしてからマージソートですね。
単純なソートはほとんどクイックソートですね。 ソートってのは速度が命ですから、遅いソートは、アルゴリズムの勉強をする以外の役にはたちません。 よって、よほど特別で明確な理由がない限り、個人がプログラムを組むときは、クイックソート以外の手法に手を出すべき局面というのもちょっと思いつきません。 プロが実務で組むときはビンソートと組み合わせたりしますが。 ちなみに、よほど特別な理由というのを、俺自身１つだけ過去に持っていたことがあります。 フリーのデータ管理ソフトを作る際に、「同一であるデータの順序を保障したい」という妙な理由で、ｐ－マージソートという特殊な手法を使っていました。 これは２次元配列を複数のキーによってソートするときに生じる問題でした。 今でもそのソフトにはｐ－マージソートが載っていますが、現在では全体処理をもっと速いアルゴリズムに変更していますので、これを使い続ける意味はなくなっています。 ですが、面倒なんでそのまま使い続けています。 クイックソートってのは、ネット上にホイホイ落ちてるようなサンプルを使うと、特殊なデータ配列のときにハングアップすることがあって、それを実務に絶えうる形に変更するのが手間だったんです。
お礼
ありがとうございます。スピードを要するデータ管理ではソートのアルゴリズムがかなり重要なのですね。具体的にはどんなデータを扱っているのでしょうか？
関連する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を選んだ) これではいけないのでしょうか。 長くなりましたが、よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- バブルソートとクイックソート
まだソートについて勉強し始めたばかりですが バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し クイックソートはそれほど増加しないのはなぜでしょうか？？ 検索してみてもプログラムが書いてあってよくわからないので... 根本的なところなのでしょうがどなたか教えてください!
- ベストアンサー
- C・C++・C#
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- クイックソートのアルゴリズムが分かりません＞＜；
C言語初心者の学習を終えて、アルゴリズムの構造を学んでいる段階のものです。バブルソートを実装することは成功したのですが、クイックソートが実装できません＞＜ 以下は文字列をバブルソートできるアルゴリズムです。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAXCHARSINONELINE 400 #define LINETABLESIZE 100 char linetable[LINETABLESIZE][MAXCHARSINONELINE]; int resultindex[LINETABLESIZE]; int maxtableindex = 0; void addToTable(char *); void initresult(); void mysort(); int mycompare(int, int); void myswap(int, int); char mark[2]; int start; int end; int main(void) { char line[MAXCHARSINONELINE]; char *ret; int i; do { ret = fgets(line,MAXCHARSINONELINE,stdin); if( ret != NULL ) { addToTable(line); } } while(ret != NULL); fprintf(stderr,"sorting...\n"); start = clock(); /* for(i=0; i<10000; i++){ */ initresult(); mysort(); /* } */ end = clock(); fprintf(stderr,"[%f sec]\n",(float)(end-start)/CLOCKS_PER_SEC); fprintf(stderr,"[results]\n"); for( i = 0; i < maxtableindex; i++ ) { printf("(L.%3d):%s",resultindex[i]+1, linetable[ resultindex[i] ]); } return 0; } void addToTable(char *data) { if( maxtableindex >= LINETABLESIZE ) { fprintf(stderr,"Table is full.!\n"); exit(0); } strncpy( linetable[maxtableindex], data, MAXCHARSINONELINE ); maxtableindex++; } void initresult() { int i; for( i = 0; i < maxtableindex; i++ ) { resultindex[i] = i; } } void mysort() { int i,j,k; for( i = maxtableindex-1; i > 0; i-- ) { for( j = 0; j < i; j++ ) { /* printf("--\n"); for(k = 0; k < maxtableindex; k++) { if((k == j) || (k == j + 1)) { strcpy(mark,"*"); } else { strcpy(mark," "); } printf("%s %s", mark, linetable[resultindex[k]]); } printf("--\n"); */ if( mycompare(j, j + 1) > 0) { /* printf("swap %d <----> %d\n",j ,j + 1); */ myswap(j, j + 1); } } } } int mycompare(int i, int j) { return strcmp(linetable[resultindex[i]], linetable[resultindex[j]]); } void myswap(int i, int j) { int tmp; tmp = resultindex[j]; resultindex[j] = resultindex[i]; resultindex[i] = tmp; } このプログラムを改編して、クイックソートにしたいのですが、どこをどうすればよいのでしょうか。 長くなってすみません。 ご回答をお願いします。
- 締切済み
- C・C++・C#
- クイックソートしながら重複要素削除アルゴリズム
アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ ている物が多く処理のイメージが沸かずクイックソートもコピペや既存 の関数で処理していて、満足に理解出来ていないのですが。 以下の問題を、お解かりになるかた教えて頂けませんでしょうか？ ■問題 2万件位の数値データの中から重複要素を削除しながら昇順または降順で、 ソートするアルゴリズム(※１) ■条件 BASIC的(※２)な記述やプログラム中のコメントなどの形式でも構いま せん出来るだけ簡単に示して頂けると助かります。 補足 (※１)ソートする際、重複要素を消すともっと処理が早くなるのではと 思ったので。 目的は、処理の速さを求める事と、次回から応用が聞くよ うにソート自体を理解したいのでクイックソートで無くても構いません。 (※２)実際に動かなくても構いません、イメージが掴みやすい方が良いと いう意味でとって下さい。
- ベストアンサー
- その他（プログラミング・開発）
- それぞれのソート方法の特徴の違いについて
ソートを勉強しているのですが、 ヒープソートや、クイックソートなど効率の良いやり方と、 バブルソートのように、そうでないものがあるらしいことを 知ったのですが、最強のアルゴリズムは存在するのですか？ それとも、ソート対象の状況によって、有効なアルゴリズムが違ってくるのですか？ もし違うとしたら、どのように違うのでしょうか。
- ベストアンサー
- C・C++・C#
- ソート（データの並べ替え）の逆概念はシャッフル？
ソートは、データの集合を一定の規則に従って並べること。 バブルソート、シェーカーソート、コムソート、選択ソート、 挿入ソート、シェルソート、ヒープソート、マージソート、 クイックソート、バケットソート、基数ソート、 逆写像ソート、ボゴソート、奇偶転置ソート、シェアソート などがあるそうです。 ではその逆概念の、データの集合を一定の規則に従ってバラバラにすることってなんといいますか? トランプ（カードマジック）でよく見かけるシャッフルのことでしょうか？ ディールシャッフル、ヒンズーシャッフル、オーバーハンドシャッフル、リフルシャッフル、ファローシャッフル などがあるそうです。 それらを数学的に扱ったものってありますか？
- ベストアンサー
- 数学・算数
- C言語、ソートの効率を考える問題について
繰り返しソートとバブルソート、改良バブルソートの中でどれが一番効率的であるかを理論的な比較回数やプログラムの量、使用するメモリの量から考えたいんですけどわかりません。教えてください。
- 締切済み
- C・C++・C#
お礼
なるほど、データ数によるのですね。