マージソートのプログラム

[クォーク]

配列を使って100個の要素をマージソートするプログラムを作成中です。
コンパイルは通りましたがソートされません.....なぜでしょうか？


また、連結リストを用いたマージソートの実装も課題としてあるので、方針としてどのようにすればいいかを助言下さると嬉しいです

コード:

#include <stdio.h>
#include <stdlib.h>

#define MAX_ELEMENTS 1000/*マージソートの作業領域の大きさ*/
#define sort_list 0 //連結リストのソートのときには1　単なる配列のソートのときには0

struct node{
	int value;//整列のキーとなる値
	struct node *next; //次のセルへのポインタ
};
int b[MAX_ELEMENTS];/*マージソートに使う作業領域*/


void merge_sort_array(int a[], int low, int high);//配列版のマージソート
void merge_sort_kozotai(kozotai a[], int low, int high);//メンバdataの整列。keyは安定かどうか見るため
struct node *merge_list(struct node *a, struct node *b);/*二つの連結リストaとbをマージする。マージされた連結リストの先頭要素へのポインタを返す*/
struct node *merge_sort_list(struct node *x);/*連結リスト版のマージソート*//*連結リストxを整列する。整列された連結リストの先頭要素へのポインタを返す*/

void error(char *s);/*エラーを出力する*/
struct node* make_node(int a);/*nodeをつくって返す*/
void insert_node(struct   node *x, struct   node *p);/*ポインタpでさされたnodeのあとにポインタxでさされたnodeを挿入する。*/

int main(void){
	struct node *node;
	struct node *list, *list_head;
	int i;


int hairetsu[100]={412, 54, 595, 329, 24, 488, 313, 272, 129, 210, 
670, 516, 342, 541, 491, 640, 167, 117, 726, 206, 
474, 762, 153, 292, 1000, 607, 151, 661, 93, 270, 
737, 531, 641, 548, 299, 287, 547, 394, 550, 475, 
443, 261, 707, 503, 403, 739, 226, 646, 778, 588, 
427, 169, 477, 572, 413, 300, 88, 321, 55, 779, 
542, 680, 211, 273, 288, 276, 405, 307, 424, 668, 
756, 255, 190, 449, 35, 435, 91, 486, 58, 408, 
4, 63, 534, 330, 701, 65, 256, 311, 586, 404, 
459, 254, 291, 333, 42, 343, 418, 512, 164, 56};

int total=100; /*table, hairetsuに登録されているデータの個数*/


	printf("整列前の配列\n");
	for(i=0;i<total;i++){//配列を表示する
		printf("hairetsu[%d]= %d\n" , i,  hairetsu[i]);
	}
	merge_sort_array(hairetsu, 0, total-1);//配列版のマージソート

	printf("\n整列後の配列\n");
	for(i=0;i<total;i++){//（ソートされた）配列を表示する
		printf("hairetsu[%d]= %d\n" , i,  hairetsu[i]);
	}

return 0;
}


struct node* make_node(int a){/*nodeをつくって返す*/
	struct node *p;

	if ((p=(struct   node*)malloc(sizeof(struct  node ))) == NULL)
		error("メモリが足りません\n");
	p->value =a; //セルに値をセットする
	p->next =NULL;
	return(p);
}


void error(char *s){/*エラーを出力する*/
	fprintf(stderr, s);
	exit(1);
}



/*配列版のマージソート。a[low]～a[high]の要素を整列する*/
void merge_sort_array(int a[], int low, int high){
int b[100];
	int m,i,j,k;
	
	if(low==high){
	return;}
	
	else{
		
		m=(low+high)/2;
		merge_sort_array(a, low, m);
	merge_sort_array(a, m+1, high);
		
	for(i=low;i<m;i++){
	b[i] = a[i];

	}
	for(i=m+1, j= high;i<=high;i++,j--){
	b[i] = a[j];

	}
	
		i = low;
		j = high;
		
		int a[1000] = {};
		for(k = low;k<= high;k++){
			if(b[i] <= b[j]){
				a[k] = b[i++];}
			else{
			a[k] = b[j--];}
			
		}
	}
	
} 

[へにっくす]

びみょーに間違ってる・・・

以下のページは参考になりますか？
C言語講座：マージソート

あとインデントはちゃんとそろえましょうね。

[みけCAT]

コード:

		int a[1000] = {};

きちんと解析してはいませんが、102行目のこれでソート対象の配列を隠して更新しないようにしているのはまずい気がします。

[クォーク]

返信ありがとうございます。

しかし、へりっくすさんのサイトを見てもどこを直せばいいのかよくわかりませんでした.....

また、102行目の部分は、配列a[]にb[]の要素を代入するので、その前に一度初期化するという意味で書きました。
それを消してもソートはうまくいきませんでした

[かずま]

78行目の int b[100]; を削除。b は 11行目にある。
102行目の int a[1000] ={}; を削除。
a は 77行目で宣言されていて、その実体は 29行目の配列。
90行目の i<m を i <= m にする。
これでどうなりますか？

[へにっくす]

まずはインデントをそろえることを覚えた方がいいですね。
HOME > PowerNews連載コラム > 第39回 プログラミングの周辺事項(2)～きれいでわかりやすいソースとは？ > 2.同じレベルの処理は字下げ位置を揃える

しかし、へりっくすさんのサイトを見てもどこを直せばいいのかよくわかりませんでした.....

No.1で掲示されているmerge_sort_array関数と
私がNo.2で示したリンク先のソースのMergeSort関数を見比べてみましょう。
最初のif文の条件からして間違っているのが分かるよね？
またMergeSort関数にあるそれぞれのコメントが、あなたが示したmerge_sort_array関数のどこにあたるのか対応付けしてみてはどうでしょうか。
「マージソート」なのだから処理の手順は同じはずです。

[クォーク]

できました、ありがとうございました！！