問題

マージソートを作成せよ。配列Aをソートせよ。（教科書 p. 52の例。問3.4 p.55)　再帰的なプログラムを作成すること

#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;


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

   /* 停止条件は、left==rightつまり、要素が1のとき。そのままで答え */
   /* 再帰条件 */
   if(left < right){
       /* ほぼ真ん中 */
       /* 前半をソート */
       /* 後半をソート */
      /* Bにマージしよう */

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

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);
}

問題

コメント

解答例