- 締切済み
Double型ソート方法
お世話になります。 VB初心者ですが宜しくお願いします。 ソートについてなのですが、Double型の配列(要素数8191)をソートしたいのですが処理が早いソート方法はあるのでしょうか。 クイックソートで試してみたのですがスタック領域が不足しています。 とのエラーメッセージが表示され処理が停止します。 スタック領域を消費しないソート方法などあればご教授宜しくお願いします。
- xxxsinxxx
- お礼率37% (3/8)
- Visual Basic
- 回答数4
- ありがとう数0
- みんなの回答 （4）
- 専門家の回答
みんなの回答
- a-saitoh
- ベストアンサー率30% (524/1722)
クイックソートは自作ですか？ プログラムを間違えているからスタックが不足するのでしょう。 再帰呼び出しの際に、ソート対象のデータのコピーを渡しているとか。 クイックソートはインプレースソートなので、8191要素くらいでスタックが足りなくなることは考えにくいです。
- imogasi
- ベストアンサー率27% (4737/17068)
＃１で示唆されている、再帰型（リカーシブな）のアルゴリスムを使っているからだと思います。 http://e-words.jp/w/E383AAE382ABE383BCE382B7E38396E382B3E383BCE383AB.html http://www.geocities.jp/kmctecyh/k_gozen/gozen03/gozenans0303.PDF にあるように 「リカーシブは、プログラムの中から自分自身を呼び出すことを言う。自分自身を定義するの に自分自身よりも１次低い集合を用いる。その部分集合はより低次の部分定義を用いて定義する ことを繰り返して表現する。 クィックソートは、適当にサンプリングして得られたデータＮに着目し、Ｎ以下のデータ系 列とＮ以上のデータ系列に分割する。このデータＮを軸(ピボット)という。データＮを軸とし て、その軸の値より小さい要素は軸より前方へ、大きな要素は軸より後方へ振り分ける。適当な 長さの系列になるまで分割を繰り返し、それぞれの系列をソートすれば１つのソート済み系列と なる。 分割の繰返しに再帰呼び出し(リカーシブ)を利用した高速の整列法である。」 ーーー 質問者がどこかで見たアルゴリズムがリカーシブなものであったのでしょう。理系の先生のクイックソートの記述には、これが多そう。 しかしすぐ質問のような事態になるでしょう。戻った時の情報を 蓄えていかないとならないから。 どこか再帰を使わないクイックソートのアルゴリズムを見つけるしかないでしょう。 http://edu.inf.shizuoka.ac.jp/lecture/2007/X121/text/AandD_I0710.pdf に考え方とC言語の簡単例がある。 「再帰的でない クイックソート」などでWEB照会しては。
- don_go
- ベストアンサー率31% (336/1059)
余計な作業領域を必要としない高速ソートとしては ↓が有ります。 コムソート(Comb Sort) http://www.ffortune.net/comp/slib/sort/combsort.htm
- t_nojiri
- ベストアンサー率28% (595/2071)
プログラム知ってれば知ってると思うんですが、treeソートやクイックソートは最低でも比較対象の2倍はメモリ必要となります。 メモリが無い状態でソートするとなると、単純ソートやバブルソートとなりますが、決してこれらのソートは速いとは言えません。 とはいえ、スタック領域が不足なんて、このくらいのデータ量で出るのか？と思い少し調べました。 http://www.drk7.jp/MT/archives/000995.html
関連するQ&A
- クイックソート
クイックソートには再帰を使わない方がいいんですか？ 再帰を使わないとすると明示的にスタックで管理することになると思うのですが，整列させたい要素数がバラバラの時はどのようにすればよいですか？
- ベストアンサー
- Visual Basic
- クイックソートで・・・
C言語で再帰を利用してクイックソートを書いたのですが、データ数が大きくなるとプログラムが途中で終了してしまいます。これってスタック領域がなくなってしまったからでしょうか？お願いします。
- ベストアンサー
- C・C++・C#
- クイックソートについて
下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }
- 締切済み
- C・C++・C#
- クイックソートで並べ替え
友人から情報処理の質問を受けました。ですが、私では良く分からなかったので質問します。 2,4,8,1,6,5,2,7,3,7の整数をクイックソートで並べ替えよ。 また、比較回数を示せ（軸要素は先頭の2要素のうち大きいほうとせよ）。 よろしくお願いします。
- 締切済み
- C・C++・C#
- 構造体配列のクイックソート
こんにちわ。 構造体配列のリストを ポインタのつなぎ変えによるクイックソートで 以下のようなソートをしたいのですが、悩んでおります。 struct info { int count; struct info *prev; struct info *next; }; int main () { struct info info[5]; /* 初期値設定 */ quick_sort(info, 0, 5); return 0; } 上記のようにして、クイックソートをしたいのですが、 よくあるクイックソートだと 例えば初期値を ＜配列のindex＞要素の値を <0> <1> <2> <3> <4> 5 1 4 3 2 などと定義した場合 普通のクイックソートだと <0> <1> <2> <3> <4> 1 2 3 4 5 というように並び変えられてしまい ＜配列のindex＞と 要素の値の組み合わせが変わってしまいますが、 この組み合わせを変えず、 struct info *if; if = info; for (i=0; i<MAX; i++){ printf("%d", if->count); if = if->next; } printf("\n"); とすることで、indexとしては昇順になっていないが *nextをたどっていくことでちゃんと目的の値の昇順になっている というのを実現したいのですが、ポインタのつなぎ変えか何かが 間違っているようで うまいことできていません。 どなたかご教授いただけますでしょうか。 申し訳ありませんが、よろしウお願いいたします。
- 締切済み
- C・C++・C#
- クイックソートがうまくいかない
クイックソートとはこういう仕様のソートのことです。 (1)バラバラの配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 自分で確かめてみたのですが、どうやら関数QuickSortの中でさらに再帰的にQuickSortにかけるときにバグが発生しているようです。ですが、なぜバグが起きるのかわかりません。 お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 void QuickSort(char mi,char *hai,int youso) { char *shoubox; char *bigbox; int k=0; int q=0; int i,len,len2; /*もし配列haiの大きさが1ならば終了*/ if(strlen(hai)==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso-1;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
- 文字列をソートする方法
数値をソートする方法にはバブルソートやクイックソートなどがあり アルゴリズムは分かるのですが 文字列を五十音順にソートしたい場合にはどのようにしたら良いですか？ 検索をかけてみたのですが、大抵プログラミング言語に備わったsortの方法が紹介されており 自分で処理を行う方法については書かれていません。 ExcelのSort機能を使わない方法で教えてください。
- ベストアンサー
- Visual Basic
- クイックソートがうまくいかない
クイックソートの仕様はこうです。 (1)バラバラにランダムで入力した配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 動作させてみたところ関数QuickSortの中の「基準値より大きいか小さいかの仕分けの処理」の後で、再帰処理があるのですが、再帰ではなく無限ループになってしまっているようです。 自分では、この処理で無限ループをとめているつもりです。 if(youso==1) { return; } なぜこのようになってしまうのでしょうか お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 int k,q; void QuickSort(char mi,char hai[10],int youso) { char shoubox[10]; char bigbox[10]; int i,len,len2; k=0,q=0; /*もし配列haiの大きさが1ならば終了*/ if(youso==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
- CObArrayのソート
CObArrayクラスの要素をソートするにはどうしたらよいでしょうか? Cライブラリのqsortを直ぐに思い浮かべたのですが、確かqsortは配列の要素だったはすだと思いました。CObArrayの動的配列に対応できるか分かりかねましたので質問したしだいです。 参考HP,別の方法があれば教えて頂きたいです。
- 締切済み
- C・C++・C#
