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

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=になっている部分に何を代入すればよいかがわかりません。
とても難しい質問だと思いますが自分では解決できなかったのでもしよろしければ教えていただけると幸いです
よろしくお願いいたします。
コマンドライン引数などについては多少は理解しております。
質問のコード追記

jimbe

2021/07/29 12:23

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

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

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

関連した質問