STEP 1.2 マージソート(merge sort)

問題 

#define N 10

 int A[N]={42,33,78,19,46,63,25,11,54,17};

とする

[実行例] 
A: 42 33 78 19 46 63 25 11 54 17 ← ソート前出力

A: 11 17 19 25 33 42 46 54 63 78　←　ソート後出力
マージソートの様子をプリントするようにして、実行を確認するとよい。 たとえば、下の実行例では、leftからrightまでがマージソートの対象で、leftからhalf, half+1からrightまでがマージされている様子をプリントしている。配列の添え字が0から始まることに注意 
A: 42 33 78 19 46 63 25 11 54 17 

Merge:left= 0, half= 0, right= 1 42 33 78 19 46 63 25 11 54 17 42 33 ** ** ** ** ** ** ** ** <- A[0]と、A[1]をマージする 
Merge:left= 0, half= 1, right= 2 33 42 78 19 46 63 25 11 54 17 <- マージ結果 33 42 78 ** ** ** ** ** ** ** <- 次は A[0] からA[1]と、A[2] 
Merge:left= 3, half= 3, right= 4 33 42 78 19 46 63 25 11 54 17 ** ** ** 19 46 ** ** ** ** ** 
Merge:left= 0, half= 2, right= 4 33 42 78 19 46 63 25 11 54 17 33 42 78 19 46 ** ** ** ** ** <- A[0]からA[2]と、A[3]からA[4] 
Merge:left= 5, half= 5, right= 6 19 33 42 46 78 63 25 11 54 17 ** ** ** ** ** 63 25 ** ** ** 
Merge:left= 5, half= 6, right= 7 19 33 42 46 78 25 63 11 54 17 ** ** ** ** ** 25 63 11 ** ** 
Merge:left= 8, half= 8, right= 9 19 33 42 46 78 11 25 63 54 17 ** ** ** ** ** ** ** ** 54 17 
Merge:left= 5, half= 7, right= 9 19 33 42 46 78 11 25 63 17 54 ** ** ** ** ** 11 25 63 17 54 <- A[5]からA[7]と、A[8]からA[9] 
Merge:left= 0, half= 4, right= 9 19 33 42 46 78 11 17 25 54 63 19 33 42 46 78 11 17 25 54 63 <- 最後はA[0]からA[4]と、A[5]からA[9] 

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

コメント

  • 教科書は「マージした結果を一旦配列Bに作り出し、配列Aに書き戻す」という方法
  • マージソートを再帰的に捉えよう
    • 停止条件　：要素が１つなら、それ自身がソート結果
    • 再帰条件　：そうでないなら、要素を前半と後半の2つに分割し、それぞれをマージソートする。2つの結果をマージした結果が答えである。
  • 分割統治法 (devide-and-conquer)
    • 問題を小さな問題に、（お互いが影響しないように）分割する。
    • 部分問題の解を統合することで、元の問題の解を得る。
    • マージソートの場合：n個の要素からなるデータをソートする　⇒　約 n/2個の要素からなるデータをソートするという2つの問題に分割。ソート結果を統合。
提出プログラムについて
  • 有名な例題ばかりなのでコードは入手できる。見るなら、しっかり読んで書けるようにしよう（よいコードを見ること！）
  • 自分なりの解答を作ってもよい。教科書の疑似コードやプログラムも理解すること。
    • 教科書と異なるコードを提出する場合は、「コードだけ送られても、読めない（読んでいる時間がありません）」。変数の役割など、コメントをつけてくれると助かります。
教科書の説明について
  • 教科書 52ページの実行過程では、配列のインデックスが1から始まるので、分割が1,2と3,4,5になっている。Cの配列では0から始まるので、0,1,2 と3,4に分かれる。プログラムにprint文を入れてマージの様子を見ていくと、52ページとは異なる分割でマージが行われる。
疑似コード中の配列に使われれている記号 : について
  • p.6の脚注に、この記法の説明あり
  • A[left:half]は、配列Aの left番要素から half番要素までの部分、と読む。
  • C言語の構文ではないので注意
配列の扱い（大域変数、引数）
  • 配列Aや配列Bを、どのような変数にするか、merge関数をどう呼び出すかによって、解答プログラムは異なったものになります　（ソートアルゴリズム大枠は、同じものです）
  • 教科書の解答は、p.55の問3.4の解答にあたるp.171を参照してください。疑似コードとかなり違う、と見えるかもしれません
[関連の例題]
例題集
  • 0904 (今日のウーミングアップ2問目;後でリンク）

解答例

[プログラム解答例] 

#include <stdio.h>

#define N 10
/* 大域変数 */
int A[N]={42,33,78,19,46,63,25,11,54,17};

/* 関数宣言 変数の型と仮引数をしっかり書いた場合 */
/* int B[]は、「intの要素を格納する配列」を宣言している */
void merge(int B[], int left, int half, int right);
void merge_sort(int left, int right);

/* 前半 (left - half)と後半(half+1 - right) をBにマージ */
void merge(int B[], int left, int half, int right){
   int i, j, k;
   i = left;
   j = half+1;

   for(k = left; k <= right; k++){
      if(i<=half && (j == right + 1 || A[i] < A[j] )){
      /* 前半に要素あり、かつ、後半には要素がないか、あるいは前半要素が小 */
          B[k] = A[i];
          i++;
      }
      else{ /* それ以外は、全て、後半より */
          B[k] = A[j];
          j++;
       }
    }
}

void merge_sort(int left, int right){
   int half, k;
   int B[N]; /* マージ用配列 */

   /* 停止条件は、left==rightつまり、要素が1のとき。そのままで答え */
   /* 再帰条件 */
   if(left < right){
      half=(right + left) / 2; /* ほぼ真ん中。-1しなくてもよい。-1では前半部を小
さく */
      merge_sort(left, half); /* 前半をソート */
      merge_sort(half+1, right); /* 後半をソート */
      merge(B, left, half, right); /* Bにマージしよう */

      /* 途中のマージ結果をプリントします */
      printf("Merge:left=%2d, half=%2d, right=%2d\n",left, half, right);
      print_arrayA(left, right); /* leftからrightの値を表示 */
      getchar(); /* 一文字入力待ち */

      /* BをAに書き戻し */
      for(k = left; k <= right; k++){
         A[k] = B[k]; /* マージ結果を大域変数の配列Aに書き戻し */
      }

   }
}

/* main 関数 */
int main(void){
   int i;

   /* 配列A ソート前。表示 */
   printf("A:");
   for(i=0; i < N; i++) {
      printf("%3d ",A[i]);
   }
   printf("\n");
   printf("\n");

   merge_sort(0, N-1); /* left=0 right=N-1までをマージソート! */

   /* 配列A、ソート後 */
   printf("A:");
   for(i=0; i < N; i++) {
      printf("%3d ",A[i]);
   }
   printf("\n");
   printf("\n");

   return(0);
}

/* マージソート時の配列の状況を表示するための関数 */
void print_arrayA(int from, int to) {
   int i;
   for (i = 0; i < N; i++) { /* 配列Aの全体 */
         printf("%2d ", A[i]);
   }
   printf("\n");
   for (i = 0; i < N; i++) { /* 配列Aのうち、ソート対象部分 */
/*      printf("A[%d] = %d ",i,  A[i]); */
      if (from <= i && i <= to)
         printf("%2d ", A[i]);
      else
         printf("** ");
   }
   printf("\n");
}