c言語　マージソートで並べ替え

nue · #1

以下のプログラムをマージソートに変換したいのですがやり方がわかりません。
詳しい方教えてください！

コード:

#include <stdio.h>
#include <string.h>


int main(void){
		FILE *fp;
		int n,work;
		
		char str[256];
		
		char team[100][100];
		char name[100][100];
		int age[100];
		double height[100];
		int votes[100]; 
		
		char a[100];
		char b[100];
		
		double s;
		int i,j,c;
		
		fp = fopen("list.txt","r");
		if(fp==NULL){
			printf("オープンできません\n");
		return 0;
		}
		
		for (n=0; n<100; n++) {
		fscanf(fp, "%s %s %d %lf %d", team[n], name[n], &age[n], &height[n], &votes[n]);
		}
		
		i=0;
		while(i<100-1){
		j=i+1;
		while(j<100){
		
		if(votes[i] < votes[j])
		{

		work = votes[i];
		votes[i] = votes[j];
		votes[j] = work;

		strcpy(a,name[i]);
		strcpy(name[i],name[j]);
		strcpy(name[j],a);

		strcpy(b,team[i]);
		strcpy(team[i],team[j]);
		strcpy(team[j],b);

		c=age[i];
		age[i]=age[j];
		age[j]=c;

		s=height[i];
		height[i]=height[j];
		height[j]=s;
		}
		j++;
		}
		i++;
	}
	
		printf("並び替えデータは\n");
		for(n=0;n<100;n++)
		printf("[%4s] %11s %d %.1f cm %d \n", team[n], name[n], (20180708-age[n])/10000, height[n], votes[n]);

		fclose(fp);

	return 0;
}

listはこのような内容になっています。
（数が多い為一部省略しています）

8 O.MOMOKA 19970920 156 26363
4 O.NANA 19971107 155 75067
8 O.NAO 19941205 159.6 21614
8 O.RIN 19961107 158.4 21798
B O.SHIDUKA 19911228 164 14488
NIII O.TUGUMI 20021215 156 20913
8 O.YUI 20011226 161 31359
NIII O.YUKA 19990216 161 81629
KII O.YUNA 20011218 155 27648
BII O.YUURI 19991201 160 33012
E S.AKARI 19911031 159 154011
A S.AYANA 19960108 154 15574
TII S.ERENA 20000912 154 17258
E S.MAYA 20000110 163 29413
M S.MIRU 19971014 160 33970
8 S.NAGISA 20001223 149 24298
M S.NAGISA 19960825 163.2 21818
E S.OKA 20020226 155 24940
BIII S.PRAEWA 20010224 158 20106
KII S.SARINA 19930118 161 48671
B S.YUKARI 19950828 159 25045
KIV S.YUKI 19980402 160 17351
KII T.AKANE 19911129 154 37773
H T.AKI 19991025 158 17558
NIII T.AYAKA 19970720 158 22292
B T.JURI 19971003 156 48100
E T.MARIKA 19960105 161 17027
B T.MEGU 19981112 161 28024
H T.MERU 20000107 163 31111
H T.MIKU 20010912 151 50175
KIV T.MIO 19980517 154 24272
NIII T.MOEKA 20010423 158 21182
H T.NATSUMI 20000810 170.4 21387
KII T.SAKI 19991124 152 23373
E T.YUKI 19950718 153 21082
S T.YUMIKO 19970924 164 19341
KIV U.HIRONA 19980809 155 17557
KII U.MIKOTO 19951114 165 25261
KIV U.NAO 19970812 157 18062
BII U.REI 20010528 151 14985
M Y.AKARI 19960816 163.5 46837
H Y.AKIYOSHI 20001024 158 19371

かずま · #2

元のプログラムは、選択ソートですね。

コード:

#include <stdio.h>

void selection_sort(int *v, int n)
{
	int t;  // 値交換用変数
	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++)
			if (v[i] > v[j])                      // 逆順なら
				t = v[i], v[i] = v[j], v[j] = t;  //   交換
}

int main(void)
{
	int a[10] = { 54, 18, 90, 36, 45, 54, 72, 27, 63, 81 };
	int t[10];
	for (int i = 0; i < 10; i++) printf(" %d", a[i]);
	putchar('\n');
	selection_sort(a, 10);
	for (int i = 0; i < 10; i++) printf(" %d", a[i]);
	putchar('\n');
}

マージソートは次のようなものです。

コード:

#include <stdio.h>

void merge_sort(int *v, int a, int b, int *t)
{
	if (a >= b) return;
	int c = (a + b) / 2;
	merge_sort(v, a, c, t);
	merge_sort(v, c + 1, b, t);
	int i, j, k = a;
	for (i = a; i <= c; i++) t[k++] = v[i];
	for (i = b; i > c; i--) t[k++] = v[i];
	i = a, j = b, k = a;
	while (i <= j) v[k++] = (t[i] < t[j]) ? t[i++] : t[j--];
}

int main(void)
{
	int a[10] = { 54, 18, 90, 36, 45, 54, 72, 27, 63, 81 };
	int t[10];  // マージソート用作業領域
	for (int i = 0; i < 10; i++) printf(" %d", a[i]);
	putchar('\n');
	merge_sort(a, 0, 10-1, t);
	for (int i = 0; i < 10; i++) printf(" %d", a[i]);
	putchar('\n');
}

元のプログラムは、たくさんのデータを交換していますが、
次のように添字の配列を用意して、それだけを交換すれば、
プログラムは簡単になり、高速にもなります。

コード:

#include <stdio.h>

#define NUM_DATA 100
#define MAX_STRING 100

int main(void)
{
	int i, j, k, n;
	int index[NUM_DATA];

	char team[NUM_DATA][MAX_STRING];
	char name[NUM_DATA][MAX_STRING];
	int age[NUM_DATA];
	double height[NUM_DATA];
	int votes[NUM_DATA];

	FILE *fp = fopen("list.txt", "r");
	if (fp == NULL) {
		printf("オープンできません\n");
		return 0;
	}
	for (n = 0; n < NUM_DATA; n++) {
		if (fscanf(fp, "%s%s%d%lf%d", team[n], name[n], &age[n],
			   &height[n], &votes[n]) != 5) break;
		index[n] = n;
	}
	for (i = 0; i < n - 1; i++)
		for (j = i + 1; j < n; j++)
			if (votes[index[i]] < votes[index[j]])
				k = index[i], index[i] = index[j], index[j] = k;

	printf("並び替えデータは\n");
	for (i = 0; i < n; i++) {
		j = index[i];
		printf("[%-4s] %-11s %d %.1f cm %d \n", team[j], name[j],
				(20180708 - age[j]) / 10000, height[j], votes[j]);
	}
	fclose(fp);
	return 0;
}

あとは、選択ソートをマージソートに書き換えるだけです。
比較用に votes のアドレスを渡す必要があります。

上記の説明を参考に、解答を作って提示してください。
分からないところがあれば、どことどこが理解できないかを
具体的に質問してもらえれば、それらに回答し、最終的な
コードも付けましょう。

かずま · #3

すみません。
選択ソートのプログラムの main にマージソート用作業領域
int t[10]; が紛れ込んでいました。これは不要でした。

添字の配列をソートするプログラムの選択ソート部分を
マージソートの呼び出しに変更するだけで解答になります。
マージソートは、votes が追加されているだけで、行数も変わっていません。

コード:

#include <stdio.h>

#define NUM_DATA 100
#define MAX_STRING 100

void merge_sort(int *v, int a, int b, int *t, int *votes)
{
	if (a >= b) return;
	int c = (a + b) / 2;
	merge_sort(v, a, c, t, votes);
	merge_sort(v, c + 1, b, t, votes);
	int i, j, k = a;
	for (i = a; i <= c; i++) t[k++] = v[i];
	for (i = b; i > c; i--) t[k++] = v[i];
	i = a, j = b, k = a;
	while (i <= j) v[k++] = (votes[t[i]] > votes[t[j]]) ? t[i++] : t[j--];
}

int main(void)
{
	int i, j, k, n;
	int index[NUM_DATA], t[NUM_DATA]; // t はマージソート用作業領域

	char team[NUM_DATA][MAX_STRING];
	char name[NUM_DATA][MAX_STRING];
	int age[NUM_DATA];
	double height[NUM_DATA];
	int votes[NUM_DATA];

	FILE *fp = fopen("list.txt", "r");
	if (fp == NULL) {
		printf("オープンできません\n");
		return 1;
	}
	for (n = 0; n < NUM_DATA; n++) {
		if (fscanf(fp, "%s%s%d%lf%d", team[n], name[n], &age[n],
			   &height[n], &votes[n]) != 5) break;
		index[n] = n;
	}
	merge_sort(index, 0, n - 1, t, votes);

	printf("並び替えデータは\n");
	for (i = 0; i < n; i++) {
		j = index[i];
		printf("[%-4s] %-11s %d %.1f cm %d \n", team[j], name[j],
				(20180708 - age[j]) / 10000, height[j], votes[j]);
	}
	fclose(fp);
	return 0;
}