構造体のバブルソート

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ksg137

構造体のバブルソート

#1

投稿記事 by ksg137 » 4年前

学校の課題なのですがあと一歩のところで行き詰まっています
質問文の通り構造体内のメンバでバブルソートをしたいのですが
なかなかうまく考えられません
とりあえず今できているだけ貼っときます

コード:

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

#define NUM 5	//学生の人数
#define ORDER 1 //0:昇順 1:降順
#define MAX 301 //ソートに使う配列の数(0点~300点)

typedef struct {
	char id[5];    //学籍番号
    int pt[3];     //各科目(3科目固定)の点数(成績)
    double ave;    //全科目の平均点]
	int sub;	   //合計点
} student;

void bucket_sort(student *, int, int);

int main(int argc, char const *argv[])
{
	FILE *fp;
	int i, j, dust = 0, score = 0;
	char name[6] = {""};
    char subject[3][64] = {"", "", ""};		//各科目名
	student s[NUM] = {};	//構造体の配列
	student *sp = s;	//配列sを指すstudent型のポインタ

	for(i = 0; i < 3; i++){
		if((fp = fopen(argv[i + 1], "r")) == NULL)
			printf("\aファイルをオープンできません。\n");
		else {
			sscanf(argv[i + 1], "%[^.]", &subject[i]);
			while((dust = fgetc(fp)) != '\n');	//1行目のスキップ
			j = 0;
			while(fscanf(fp, "%[^,],%d", name, &score) != EOF){
				fgetc(fp);
				strcpy(sp[j].id,name);
				(sp[j].pt[i]) = score;
				(sp[j].sub) += score;
				j++;
			}
		}
		fclose(fp);
	}

	for(i = 0; i < NUM; i++)
		sp[i].ave = (double)sp[i].sub / 3.0;

	bucket_sort(sp, NUM, ORDER);

	if((fp = fopen(argv[4], "w")) == NULL)
		printf("\aファイルをオープンできません。\n");
	else {
		fprintf(fp,"studnt,%s,%s,%s,average\n", subject[0], subject[1], subject[2]);
		for(i = 0; i < NUM; i++)
			fprintf(fp,"%s,%d,%d,%d,%.1f", s[i].id, s[i].pt[0], s[i].pt[1], s[i].pt[2], s[i].ave);
		fprintf(fp, "\n");
	}
	fclose(fp);

	return 0;
}

//この中身がわかりません
void bucket_sort(student std[], int number, int x)
{

}
こういう要件です→http://goo.gl/To6WVf

プログラミングは1年やってますが
学校ではまだメインではないので知っていることは少ないです

丸々の答えでももちろんありがたいのですが考え方や各部の役割を
少しづつ教えていただけるとありがたいです

初めて利用させていただくので至らぬ点もあると思いますがよろしくお願いします

ksg137

Re: 構造体のバブルソート

#2

投稿記事 by ksg137 » 4年前

すみません
バブルソートじゃなくてバケットソートです(;・∀・)

chop.chop
記事: 36
登録日時: 4年前

Re: 構造体のバブルソート

#3

投稿記事 by chop.chop » 4年前

始めまして、chop.chopと申します。

バケットソートと聞いて、「おや?これは自分がつい昨日ほどに実装したものじゃないか」と思ったので稚拙ながら解説させてもらいます。

ある構造体のメンバ変数(ここではint型の数字としましょう)を使ってバケットソートする場合、以下の考え方を用いてソートすることが出来ます。
構造体studentが3こあったとして、それぞれがa,b,c君だとしましょう。点数は次のようになっているとします。
----------------------
a:98
b:80
c:70
----------------------
この点数を昇順にバケットソートする場合、まず単にstudent型構造体を指すポインタだけを持った構造体を考え、それを0~9の添え字を持つ配列として定義します。
この構造体の名前をLISTとしましょう。すると
----------------------
LIST[0]
LIST[1]
LIST[2]
...
LIST[9]
----------------------
のような配列が考えられます。
それでは格student構造体(生徒)の点数の下の位の数字に注目してみましょう。
a君は98の8、よって
----------------------
LIST[0]
LIST[1]
LIST[2]
LIST[3]
LIST[4]
LIST[5]
LIST[6]
LIST[7]
LIST[8]==>a
LIST[9]
----------------------
b君は81の1、よって
----------------------
LIST[0]
LIST[1]==>b
LIST[2]
LIST[3]
LIST[4]
LIST[5]
LIST[6]
LIST[7]
LIST[8]==>a
LIST[9]
----------------------
c君は71の1となりますが、バケットソートでは以下のようにします
----------------------
LIST[0]
LIST[1]==>b==>c
LIST[2]
LIST[3]
LIST[4]
LIST[5]
LIST[6]
LIST[7]
LIST[8]==>a
LIST[9]
----------------------
さて、ここまで出来上がると今度はLIST[0]からLSIT[9]まですべてをつなげてみましょう。
すると
----------------------
b
c
a
----------------------
という順が出来ていますね。これで一番したの位の処理は終わり、次の位に移ります。
上と同じような操作(b,c,aの順番に点数の10の位をみていく)をすると
bの81の8,cの71の7,aの91の9、に注目し
----------------------
LIST[0]
LIST[1]
LIST[2]
LIST[3]
LIST[4]
LIST[5]
LIST[6]
LIST[7]==>c
LIST[8]==>b
LIST[9]==>a
----------------------
が出来上がります。これをまたLIST[0]からLIST[9]まで繋げると、
----------------------
c
b
a
----------------------
の順番になっていることと思います。(昇順)

以上がバケットソートの基本的な考え方となります。
たとえ
----------------------
100
90
1
----------------------
のような点数であっても
----------------------
100
090
001
----------------------
とすれば問題なくバケットソートは出来ます。

ksg137

Re: 構造体のバブルソート

#4

投稿記事 by ksg137 » 4年前

はじめまして
回答ありがとうございます

なるほど、桁ごとに考えるのですね
また考えを練ってきます!

閉鎖

“C言語何でも質問掲示板” へ戻る