STEP 1.1 マージ (merge)

問題

a1[] = {19, 33, 42, 46, 78} 
a2[] = {11, 17, 25, 54, 63}

とするとき、マージ結果は

b[] = {11,17,19,25,33,42,46,54,63,78}

[実行例]

(a1とa2は、プログラム中に書いておくことにする)

a1: 19 33 42 46 78

a2: 11 17 25 54 63

b: 11 17 19 25 33 42 46 54 63 78

[コメント]
  • a1から代入する場合とa2から代入する場合の場合分けを、しっかりまとめること。
    • 上の例では、先にa2の要素がbに全て代入される。
  • いろいろな表現方法があってよい。自分の解答だけでなく、教科書や参考書にある標準的な解答も確認すること。
    • 自分と異なるプログラムは読んで比較しよう。「これなら、俺の方がいいよ」ってこともある。
  • 以下、この例題では扱わない。
    • 要素数を入力し、配列用メモリを動的に確保する方法 (calloc関数)
    • 大域変数ではなく、配列のアドレスを引数に使う方法 (例題集を)
[関連の例題]
例題集ページ
  • 0403 (今日のウーミングアップ1問目;後でリンクします)

解答例

[プログラム (mergeに、二種類のコード) ]

#include <stdio.h>


/* 配列のサイズを決めておく */
#define M 5
#define N 5

/* 大域変数 よくわかるC (p.46) */
int a1[M] = {19, 33, 42, 46, 78};
int a2[N] = {11, 17, 25, 54, 63};
int b[M+N];

/* 関数の宣言 (p.43) */
void merge(int, int);


int main (void) {
   int i;

   /* 配列a1のプリント 配列とforループの定番プログラム*/
   printf("a1:");
   for(i=0; i < M; i++) {
     printf("%3d ",a1[i]);
   }
   printf("\n");
   printf("\n");

   /* 配列a2のプリント */
   printf("a2:");
   for(i=0; i < N; i++) {
     printf("%3d ",a2[i]);
   }
   printf("\n");
   printf("\n");

   /* マージして */
   merge(M, N);

   /* 配列bのプリント */
   printf(" b:");
   for(i=0; i < M+N; i++) {
     printf("%3d ",b[i]);
   }
   printf("\n");
   printf("\n");

   return (0);
}

/* 教科書の疑似コードに対応した merge。こちらも読めるように。配列にアクセスする前のチェックに注意 */
void merge(int m, int  n) {
   int i, j, k;

   i = 0; /* a1の添え字 */
   j = 0; /* a2の添え字 */

   /* kはbの添え字 先頭からa1かa2の要素を代入していく */
   for (k = 0; k < m+n ; k++) {

      /* a1の要素を代入する場合とは? 下のプログラムは、いろいろな表現があってよいが、教科書を読めるように */
      /* iはmより小さい(つまり、iはa1内の添え字。最後の要素を超えていない) かつ a2の要素がないか、a1の要素がa2の要素より小さい*/
      if (i < m && (j == n || a1[i] < a2[j])) {
          b[k] = a1[i];
          i++;
      }
      else { /* そうでないから、a2の要素を代入   : a1の要素がない。a2のほうが大きい */
          b[k] = a2[j];
          j++;
      }
   }
}

/* このタイプのコードもよく見る。①両方とも要素があるから、比較。
 ② a1しか残っていない場合 ③ a2しか残っていない場合。②③が不十分な解答、多数 */ 
void merge(int m, int  n) {
   int i, j, k;

   i = 0; /* a1の添え字 */
   j = 0; /* a2の添え字 */

   /* kはbの添え字 先頭からa1かa2の要素を代入していく */
   while (i < m && j < n) { /* a1, a2ともに要素が残っている */
      if (a1[i] < a2[j]) { /* a1の要素がa2の要素より小さいなら、a1から */
          b[k] = a1[i];
          i++;
      }
      else { /* そうでないから、a2の要素を代入  */
          b[k] = a2[j];
          j++;
      }
      k++;
   }

   /* whileで書いてもよいでしょう */
   for (; i < m; i++) { /* a1が残っている場合。全てa1から代入 */
      b[k]  = a1[i];
      k++;
   }

   for (; j < m; j++) { /* a2が残っている場合。全てa2から代入 */
      b[k]  = a2[j];
      k++;
   }
}