質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

マージ

複数のデータベースやファイル、プログラムなどを決まった手順や規則に従って一つに結合すること。

コマンドライン

コマンドライン(別名:Command Line Interface)は、ユーザに命令の入力を促す(プロンプト)文字列の表示を行い、すべての操作をキーボードを用いて文字列を打ち込む事でプログラムを走らせるユーザインターフェースです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

解決済

3回答

1109閲覧

キャッシュを利用したマージソート

linkinpark

総合スコア42

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

マージ

複数のデータベースやファイル、プログラムなどを決まった手順や規則に従って一つに結合すること。

コマンドライン

コマンドライン(別名:Command Line Interface)は、ユーザに命令の入力を促す(プロンプト)文字列の表示を行い、すべての操作をキーボードを用いて文字列を打ち込む事でプログラムを走らせるユーザインターフェースです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

0グッド

0クリップ

投稿2021/07/29 10:25

編集2021/07/30 09:55

C

1コード 2#include <stdio.h> 3#include <stdlib.h> 4#include <string.h> 5 6void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){ 7 int i,j,k; 8 for(i = first; i < half; i++) cache[i] = data[i]; 9 for (j = last; i < last; i++) cache[i] = data[--j]; 10 for (i--, j = first, k = first; k < last; k++) 11 data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--]; 12} 13 14void mergeSort(int *data,int *cache,int first,int last){ 15 int half; 16 17 if(last-first<=1) return; 18 half=(first+last)/2; 19 mergeSort(data,cache,first,half); 20 mergeSort(data,cache,half,last); 21 mergeSortedDataByCathe(data,cache,first,last,half); 22} 23int main(int argc,char*argv[]){ 24 int i,count,maxsize,*data,*cache; 25 FILE *fp; 26 27 if(argc!=3){ 28 fprintf(stderr,"Usage: %s <maxsize> <filename>\n",argv[0]); 29 return 1; 30 } 31 32 maxsize=atoi(argv[1]); 33 if((fp=fopen(argv[2],"r"))==NULL){ 34 fprintf(stderr,"File %s is not found\n",argv[2]);//標準エラー出力(printfと動きは同じ) 35 return 1; 36 } 37 if((data=(int*)calloc(maxsize,sizeof(int)))==NULL){ 38 fprintf(stderr,"Out of memory\n"); 39 return 1; 40 } 41 if((cache=(int*)calloc(maxsize,sizeof(int)))==NULL){ 42 fprintf(stderr,"Out of memory\n"); 43 return 1; 44 } 45 for(count=0;count<maxsize;count++){ 46 if(fscanf(fp,"%d",&data[count])==EOF) break; 47 } 48 mergeSort(data,cache,0,count); 49 for(i=0;i<count;i++){ 50 printf("%d\n",data[i]); 51 } 52 return 0; 53} 54プログラム追記マージソート 55#include <stdio.h> 56#define N 10 57 58void merge(int *A, int nA, int *B, int nB, int i, int *C) 59/* 整列配列A[0],...,A[nA-1]とB[0],...,B[nB-1]を併合し整列配列 60C[i],...,C[i+nA+nB-1]に入れる */ 61{ 62 int iA, iB, iC; /* iAはAの添字、iBはBの添字、iCは合計 */ 63 64 iA=iB=iC=0; /* 併合の開始 */ 65 while(iC <= nA+nB-1) 66 { 67 if(iA>=nA) {C[i+iC]=B[iB]; iB=iB+1;} /* Aは既に空 */ 68 else 69 { 70 if(iB>=nB) {C[i+iC]=A[iA]; iA=iA+1;} /* Bは既に空 */ 71 else /* A[iA]とB[iB]の小さい方をCへ移す */ 72 { 73 if(A[iA]<=B[iB]) {C[i+iC]=A[iA]; iA=iA+1;} 74 else {C[i+iC]=B[iB]; iB=iB+1;} 75 } 76 } 77 iC=iC+1; 78 } 79 return; 80} 81 82 83void mergesort(int *A, int i, int j) 84/* 配列A[i],...,A[j]をマージソートにより整列 */ 85{ 86 int k, n, n1, n2, mid; 87 int A1[N], A2[N]; 88 89 n=j-i+1; /* 配列のサイズ */ 90 if(n>1) 91 { 92 mid=i+(n-1)/2; /* 中央値により前後の部分配列へ分割 */ 93 mergesort(A, i, mid); /* 前半の整列 */ 94 mergesort(A, mid+1, j); /* 後半の整列 */ 95 n1=mid-i+1; 96 for(k=i; k<=mid; k++) A1[k-i]=A[k]; /* A1は前半の部分配列 */ 97 n2=j-mid; 98 for(k=mid+1; k<=j; k++) A2[k-mid-1]=A[k]; /* A2は後半の部分配列 */ 99 merge(A1, n1, A2, n2, i, A); /* A1とA2の併合 */ 100 } 101 return; 102} 103 104 105 106 107int main (void) { 108 int array[N] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 }; 109 int i; 110 111 printf("print array \n"); 112 for (i = 0; i < N; i++) { printf("%d ", array[i]); } 113 printf("\n"); 114 115 mergesort(array, 0, N); 116 117 printf("print array \n"); 118 for (i = 0; i < N; i++) { printf("%d ", array[i]); } 119 printf("\n"); 120 121 return 0; 122}

mergeSortedDataByCatheの部分には部分的に並べ替えられたdata配列についてcacheを用いて昇順にマージソートする
プログラムとdata=とcache=になっている部分に何を代入すればよいかがわかりません。
とても難しい質問だと思いますが自分では解決できなかったのでもしよろしければ教えていただけると幸いです
よろしくお願いいたします。
コマンドライン引数などについては多少は理解しております。
質問のコード追記

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jimbe

2021/07/29 12:23

data= や cache= はともかく、「cacheを用いて昇順にマージソート」というのは一体何でしょう。cache をどう用いるのでしょうか。
linkinpark

2021/07/30 01:46

申し訳ございませんが、そこがわからないところで質問にお答えできません。
guest

回答3

0

textへのデータの入力を数値を横並びにするのではなく縦順にした後、
上記のプログラムを使用することによって解決

投稿2021/07/31 16:31

linkinpark

総合スコア42

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

C

1void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){ 2 for (i = first; i < half; i++) cache[i] = data[i]; 3 for (j = last; i < last; i++) cache[i] = data[--j]; 4 for (i--, j = first, k = first; k < last; k++) 5 data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--]; 6}

コンパイルエラーは自分で修正してください。
他も修正しないと動きません。

追記
デバッグ用に printf を追加した mergeSortedDataByCahce です。

C

1void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){ 2 int i, j, k; 3 4 printf("[%d %d %d] {", first, half, last); 5 for (i = first; i < half; i++) printf(" %d", data[i]); 6 printf(" |"); 7 for (; i < last; i++) printf(" %d", data[i]); 8 printf(" }\n"); 9 10 for (i = first; i < half; i++) cache[i] = data[i]; 11 for (j = last; i < last; i++) cache[i] = data[--j]; 12 for (i--, j = first, k = first; k < last; k++) 13 data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--]; 14 15 printf("sort {"); 16 for (i = first; i < last; i++) printf(" %d", data[i]); 17 printf(" }\n"); 18}

これで 3 8 3 8 9 2 9 2 1 をソートすると、次のようになりました。

text

1[0 1 2] { 3 | 8 } 2sort { 3 8 } 3[2 3 4] { 3 | 8 } 4sort { 3 8 } 5[0 2 4] { 3 8 | 3 8 } 6sort { 3 3 8 8 } 7[4 5 6] { 9 | 2 } 8sort { 2 9 } 9[7 8 9] { 2 | 1 } 10sort { 1 2 } 11[6 7 9] { 9 | 1 2 } 12sort { 1 2 9 } 13[4 6 9] { 2 9 | 1 2 9 } 14sort { 1 2 2 9 9 } 15[0 4 9] { 3 3 8 8 | 1 2 2 9 9 } 16sort { 1 2 2 3 3 8 8 9 9 }

ソートされていますよね。
変数の値の変化を見るとはこういうことです。

追記2
質問の最後に「質問のコード追記」とあるのに、コードがない、
と思ったら、元のコードに追記したんですね。
そんなことをされたら、四角い枠の右上の + ボタンでコードをコピペ
しようとしたとき、要らないコードの削除が必要になります。
別のコードとして追記してもらいたかった。
また「コード」や「プログラム追記マージソート」という文字列も
枠の外に書くようにしてください。

その追記マージソートですが、問題があります。
#define N 10 の 10 を別の値にしてみてください。
もちろん int array[N] = { ... }; のデータも変更します。
実行結果には変な数値が現れたりしませんか?

void mergesort(int *A, int i, int j) の j はソートしたい配列の
最後の要素の添字です。
しかし、main の呼び出し元では mergesort(array, 0, N);
配列の最後の要素の次の添字 N を渡しています。
これは N-1 にしないといけないでしょう。
N を渡すと、配列の範囲外の要素をアクセスし、未定義動作となります。

次に、関数 mergesort は内部で int A1[N], A2[N]; という配列を確保しています。
mergesort は再帰呼出しをしますから、呼び出しごとにスタック上に配列が
どんどん確保され、N が大きい場合、その確保に失敗する恐れがあります。

この問題を回避するために、main で確保した A1[N] と A2[N] をポインタで
渡してやれば、mergesort は新たな領域を確保する必要がなくなります。

cache を使うほうのマージソートはそれを行っているのです。
A1 と A2 には分割されたデータが入るので 2つは要りません。
1つの cache の中を使えばすみます。

では、
void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half)
の説明をします。

ここで渡されるデータは、main の配列 data の添字が first から half-1 までと
half から last-1 までの 2つの領域です。
この 2つのデータは既にソートされています。
それらをマージして、data の first から last-1 までに入れて返します。

前半部分は cache の first から half-1 までにそのままコピーしますが、
後半部分は cache の half から last までに data の後半部分を逆順に入れます。
すると 3つめの for文でマージするときに、2つのソート済みデータの末尾を
気にする必要がなくなります。
先に末尾に達したほうの添字は、もう一方の末尾の添字になるので、
残りのデータは問題なく data に収容されます。

投稿2021/07/30 00:18

編集2021/07/30 14:31
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

linkinpark

2021/07/30 01:45

ありがとうございます。 もしまた機会がありましたらよろしくお願いいたします。
kazuma-s

2021/07/30 01:54

コンパイルエラーはどう修正したんですか? 他はどう修正したんですか? mergeSortedDataByCathe のコードの意味理解しましたか?
linkinpark

2021/07/30 02:20

下の方を参考に修正していました 肝心のコードの部分です今のところ理解できていません。 もしよろしければ教えていただけると幸いです。
kazuma-s

2021/07/30 02:27

> 下の方を参考に修正していました それは、「他はどう修正したんですか?」の回答ですね。 私のコードのコンパイルエラーはどう修正したんですか? コードの意味は理解できていなくても、 コードがどう動くのかは分かっていますか? for文や 3項演算子?: が分からないのですか?
linkinpark

2021/07/30 02:30

コンパイルエラーは自分のパソコンでは発生していません。 ただ正しく動いていないので修正しようとしています
kazuma-s

2021/07/30 02:37

「コンパイルエラーにはならないが正しく動いていないコード」を質問に追記してください。 非常に興味があります。検証したいので、コマンドライン引数に指定した maxsizeの 値と、 ファイルのデータも追記をお願いします。そうすれば、私のコードの説明をします。
linkinpark

2021/07/30 02:43

void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){ int i,j,k; for(i = first; i < half; i++) cache[i] = data[i]; for (j = last; i < last; i++) cache[i] = data[--j]; for (i--, j = first, k = first; k < last; k++) data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--]; } void mergeSort(int *data,int *cache,int first,int last){ int half; if(first==last||first+1==last) return; half=(first+last)/2; mergeSort(data,cache,first,half); mergeSort(data,cache,half,last); mergeSortedDataByCathe(data,cache,first,last,half); }
linkinpark

2021/07/30 02:44

answer27-3.exe 9 text2.txt text2の内容は383892921です
linkinpark

2021/07/30 02:45

ソートの部分がうまくいっていないと思っています。 コードの部分の説明お願いいたします。
kazuma-s

2021/07/30 04:40

「私のコードのコンパイルエラーはどう修正したんですか?」に対して なぜ、「int i, j, k; 」を追加しましたと答えないんですか? > ただ正しく動いていないので修正しようとしています 「正しく動いていない」だけでは分かりません。 どうなったかを書いてください。 Segmentation fault などのエラーメッセージを出して止まったとか、 結果が何も表示されないとか、間違った結果が表示されたとか。 「正しく動いていないコード」を質問に追記してください。」 と書いたのに、質問に追記せず、コメントに書いたのはなぜですか? コメント欄では、コードが崩れて表示されます。 検証したいのに、一部のコードしか見せないのはなぜですか? 正しく動かない原因が他の部分にあるかもしれないのに。 > text2の内容は383892921です text2.txt と text2 は違うものです。 「383892921」と「3 8 3 8 9 2 9 2 1」とは違うものです。 私が検証した時の質問のコードの修正箇所は、 - コメントの前の全角スペースの削除。2か所。 - 関数mergeSortedDataByCathe を私のコードにし、int i, j, k; を追加。 - 関数 mergeSort の中の最初の if文を if (last - first <= 1) return; に変更 - main の「わからない」を「malloc(maxsize * sizeof(int))」に変更。 - //mergeSort(data,cache,0,count); の // を削除 これで思い通りに動きました。 さて、私のコードを説明したいのですが、何が分からないのかを教えてください。 for文に { と } がないことですか? 3項演算子 ? : が分からないのですか? --j や i++ が分からないのですか?
linkinpark

2021/07/30 06:18

質問に追加しなかった部分は申し訳ございません。 他の部分のコードは正しく動いていると自分で確認したのでのせていませんでした。 また自分の実行結果はソートされていない状態でtextの内容そのままで出てきます。 思い通りというのはソートされた状態で出力されたということですか?
kazuma-s

2021/07/30 07:03 編集

> 他の部分のコードは正しく動いていると自分で確認したのでのせていませんでした。 どうやって確認したのですか? デバッグしてますか? printf で変数の値の変化を見ていますか? デバッガでステップ実行して、変数の値の変化を見ていますか? 私の思い通りとは、ソートされたものが出力されました。 ただ、表示結果の 1行目が argc=31 で argc=3 とソート結果の先頭の 1 が くっついていましたが、コード通りなので思い通りとしました。 私が検証した時の質問のコードの修正をコメントに書きましたが、 その内容は確認しましたか? それと、私のコードの何が分からないのかと尋ねているのですが。
linkinpark

2021/07/30 08:34

printfなどで値を確認しております。 最初のfor文からなぜそのようにcacheに代入しているのかがわかりません つまりcacheを用いるとはどういうことを意味するのかが分かりません。 普通のマージソートと比べてどのような利点があるのでしょうか? 質問ばかりで申し訳ございません。けれど調べてもわからないので質問させて頂いてます。 よろしくお願いいたします。
kazuma-s

2021/07/30 09:01

普通のマージソートなら分かるんですよね。そのコードを質問に追記してください。 それを元に chache がどういう意味を持つのかを説明します。
linkinpark

2021/07/30 09:55

質問に追記させて頂きました。 よろしくお願いいたします。
linkinpark

2021/07/31 08:04

コード+でコピーできるとは知りませんでした。次から気を付けていきます。 コードに関するアドバイスありがとうございます。 それからお話されている要点としてはcacheを用いることによって 再帰呼び出しによって新たな配列を確保する必要がなくなりコードの効率性が上がるという認識であっていますか?
kazuma-s

2021/07/31 16:20

コードの効率には、速度が速くなるのと、メモリー使用量が小さくなるのとが あります。今回は後者です。 これとは別に、分かりやすいコードにすると、開発効率や保守効率が上がる といったこともあります。 ところで、解決済みになっていますが、 「自分の実行結果はソートされていない状態でtextの内容そのままで出てきます」 という問題をどのように解決したのかを書かないと解決済みと言えないでしょう。
linkinpark

2021/07/31 16:28 編集

了解しました!! textのデータが横並びになっていたため整列されていないと勘違いしていただけでした。
guest

0

こんな感じやないですかね。
dataの2つのソート済み範囲[first,half)と[half,last)をマージすると考える。
cacheは名前に反してワーキングメモリっぽい感じ(前回値を使ったりしてないのでcache感がでない)。

C

1void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){ 2 int li = first; 3 const int le = half; 4 int ri = half; 5 const int re = last; 6 7 int di=0; 8 for( ; di < (last-first); di++){ 9 int useright 10 = ( li == le ) ? 1 11 : ( ri == re ) ? 0 12 : data[li] > data[ri]; 13 14 cache[di] = useright ? data[ri++] : data[li++]; 15 } 16 memcpy( data+first, cache, (last-first)*sizeof(int));} 17...18 if((data=(int*)calloc(maxsize, sizeof(int)))==NULL)...19 if((cache=(int*)calloc(maxsize, sizeof(int)))==NULL)...

ただし、mergeSortのなかのif文は修正しないと無限ループやで。

C

1 if(first==last || first+1 == last ) return;

投稿2021/07/29 14:59

matukeso

総合スコア1590

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jimbe

2021/07/29 15:06

このような穴埋めはどこかの課題の可能性がありますので、あまりさっくりコードを出してしまうのは如何かと^^;
linkinpark

2021/07/30 02:46

大学院試験の過去問で調べてもわからないので質問させて頂きました。( ´∀` )
linkinpark

2021/07/30 02:46

返信ありがとうございました。 また機会がありましたらよろしくお願いいたします。
matukeso

2021/07/30 03:40

入試なら、最初に[first,half)をcacheにコピーして、cache[0,half-first)とdata[half,last)をdata[first,last)にマージする戦略のほうがいいかな。 その場合はcacheのcallocはmaxsize/2で質問意味がでてくる。
jimbe

2021/07/30 03:45

過去問でしたか、失礼しました。
linkinpark

2021/07/30 06:10

matukesoさんありがとうございます!!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問