過去ログ
No．１３２１ マージソートについて
[戻る] [ホームページ]No.17755 |
マージソートについて 投稿者---Kei(2004/11/04 04:03:56) |
||
C言語でのことなのですが、自分なりに１０００００個の数字のはいったファイルを 作ってそれを読み込んでからマージソートでそーとするという単純な試みをやってみました。 読み込むまでのプログラムは #include <stdio.h> #define SUJI 100000 main(int argc, char *argv[]){ int A[SUJI]; int a; FILE *in_file; in_file = fopen(argv[1], "r"); if(in_file == NULL){ printf("%s: Cannot open %s\n", argv[0], argv[1]); exit(-1); } for(a=0; a<100000; a++) { fscanf(in_file, "%d", &A[a]); } とここまではうまくいったんですがその後の肝心のマージソートがよくわかりません。 疑似コードは手元にあるし、トランプ等で実際にやってみてマージソートの仕組みは理解してます。 このあとどうかいたらいいのでしょうか？ |
|||
| No.17758 |
Re:マージソートについて 投稿者---あかま(2004/11/04 06:08:22) |
||
>とここまではうまくいったんですがその後の肝心のマージソートがよくわかりません。 >疑似コードは手元にあるし、トランプ等で実際にやってみてマージソートの仕組みは理解してます。 >このあとどうかいたらいいのでしょうか？ ぬぅ。難しい質問だ。 >このあとどうかいたらいいのでしょうか？ ぶっちゃけあとはマージソートの関数を書けばいいのですが。 マージソートの仕組みを理解している→マージソートを教える必要がない。 擬似コードがある→完成一歩手前。これ以上明確なヒントもない。 しかし >その後の肝心のマージソートがよくわかりません。 それでもよく分からないとはこれいかに。 もうちょっと具体的にどこが分からないか書けますか？ 関数の書き方が分からないとか、配列を関数に渡せないとか。 でないとこれはもう答えを書くしか。 |
|||
| No.17766 |
Re:マージソートについて 投稿者---Kei(2004/11/04 11:09:22) |
||
疑似コードに Merge-Sort(A, p, r) if(p>r){ q=p+r/2 } Merge-Sort(A, p, q) Merge-Sort(A, q+1, r) この部分でトランプでは説明できても関数にはとなると、混乱しています。 |
|||
| No.17767 |
Re:マージソートについて 投稿者---ＲＥＥ(2004/11/04 11:40:04) |
||
>疑似コードに (略) >この部分でトランプでは説明できても関数にはとなると、混乱しています。 どの部分で混乱しているのですか？ 具体的に示してください。 もし、疑似コードが再帰になっているから混乱しているのであれば、 C言語でも同様に再帰で関数を呼べますので、気にする必要はありません。 |
|||
| No.17765 |
Re:マージソートについて 投稿者---επιστημη(2004/11/04 09:56:11) |
||
>疑似コードは手元にあるし、トランプ等で実際にやってみてマージソートの仕組みは理解してます。 ……その擬似コードとやらをCに翻訳するだけでしょうに。 トランプでやってみたのなら、 - カードをめくる → ファイルから読み込む - カードを山に置く → ファイルに書き込む とすればいい。 |
|||
| No.17772 |
Re:マージソートについて 投稿者---かずま(2004/11/04 14:02:32) |
||
> C言語でのことなのですが、自分なりに１０００００個の数字のはいったファイルを > 作ってそれを読み込んでからマージソートでそーとするという単純な試みをやってみました。 【掲示板ご利用上の注意】に従わず、左詰めになった見にくいプログラムを 投稿する質問には答えないつもりでいるのですが、他の回答者が 100000個の データ数について何もふれていないのが気になったので、参考となるプログラム を書いてみました。 質問者にお願いですが、次のプログラムで、関数 merge_sort の中の static がある場合とない場合で実行結果がどうなるかを報告してください。
#include <stdio.h>
#include <string.h>
#define SIZE 100000
void merge_sort(int *a, int p, int q)
{
static int b[SIZE]; int r, i, j, k;
if (p >= q) return;
r = (p + q) / 2;
merge_sort(a, p, r);
merge_sort(a, r+1, q);
for (i = p; i <= r; i++) b[i] = a[i];
for (j = q; i <= q; i++) b[i] = a[j--];
for (i = j = p, k = q; i <= q; i++)
a[i] = (b[j] < b[k]) ? b[j++] : b[k--];
}
int main(int argc, char *argv[])
{
int a[SIZE], n, i; FILE *fp;
if (argc != 2) return 1;
fp = fopen(argv[1], "r");
if (fp == NULL) {
printf("%s: Cannot open %s\n", argv[0], argv[1]);
return 1;
}
for (n = 0; n < SIZE; n++)
if (fscanf(fp, "%d", &a[n]) != 1) break;
merge_sort(a, 0, n-1);
for (i = 0; i < n; i++) printf("%d\n", a[i]);
return 0;
}
|
|||
| No.17773 |
Re:マージソートについて 投稿者---επιστημη(2004/11/04 14:36:54) |
||
Keiさんに確認したい。全データを読み込んで、メモリ上でマージソートするんでしょうか? それともファイルに置いたまま、ディスク上でマージソートしたいのでしょうか? |
|||