ソートアルゴリズム（ｃ言語）

この問題の番号の並び替えがどうしても分かりません。とき方を教えてください。

問題：ｎこの学生番号と音楽の点数からなる成績データを入力し、成績の順にデータを並び替えるプログラムを作りなさい。

入力　　　　　　　　　　　　　出力
１０　　　　　　　　　　　　　ソート前データ
１　５６　　　　　　　　　　　番号　　音楽
２　４７　　　　　　　　　　　１　　　５６
３　８５　　　　　　　　　　　２　　　４７
４　５７　　　　　　　　　　　３　　　８５
５　９６　　　　　　　　　　　４　　　５７
６　７５　　　　　　　　　　　５　　　９６
７　８１　　　　　　　　　　　６　　　７５
８　３１　　　　　　　　　　　７　　　８１
９　５０　　　　　　　　　　　８　　　３１
１０　７６　　　　　　　　　　９　　　５０
　　　　　　　　　　　　　　１０　　　７６
　　　　　　　　　　　　　　ソート後データ
　　　　　　　　　　　　　　番号　　　音楽
　　　　　　　　　　　　　　５　　　　９６
　　　　　　　　　　　　　　３　　　　８５
　　　　　　　　　　　　　　７　　　　８１
　　　　　　　　　　　　　　１０　　　７６
　　　　　　　　　　　　　　６　　　　７５
　　　　　　　　　　　　　　・　　　　・
　　　　　　　　　　　　　　・　　　　・
　　　　　　　　　　　　　　（省略）
大変だとは思いますが、お願いします。

No.5 ベストアンサー 回答者： ymmasayan 回答日時： 2003/09/08 11:56

No.4です。

ミスがありました。すみません。
ご迷惑を掛けたNo.1さんにお詫びし訂正します。

＞No.1の方の回答に補足します。

＞i,jをループ用変数とし
＞i=0～n-1　　nはデータ行数
＞j=i+1～n

これではうまくソートが出来ません。n-1はn-2のはずですね。これは基本選択法です。

バブルソート(隣接交換法）なら
i=n-2～0,-1
j=0～i
で　(j)　と　(j+1）　を比べて逆転を入れ替えます。

この回答へのお礼

皆さんありがとうございました！自分で考えていたところ解答が分かりましたので報告しておきます。なお、ポイントは、特に一生懸命考えてくれたと思う方に方に差し上げようと思います。

<解答>
#include<stdio.h>
void main(void){
int d[100],c[100],n,a[100],i,j,x,y,max;
printf("n:");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&a[i],&d[i]); }
printf("ソート前データ\n");
printf("番号　音楽\n");
for(i=0;i<n;i++) printf("%d %2d\n",a[i],d[i]);
for(i=0;i<n-1;i++){
max=i;
for(j=i+1;j<n;j++)
if(d[max]<d[j]) {max=j; }
x=d[i]; d[i]=d[max]; d[max]=x;
y=a[i]; a[i]=a[max]; a[max]=y;
}
printf("\nソート後データ\n");
printf("番号　音楽\n");
for(i=0;i<n;i++){
printf("%2d %2d\n",a[i],d[i]);
}}

お礼日時：2003/09/09 07:09

No.4 回答者： ymmasayan 回答日時： 2003/09/08 10:52

No.1の方の回答に補足します。

＞i,jをループ用変数とし
＞i=0～n-1　　nはデータ行数
＞j=i+1～n

これではうまくソートが出来ません。これはソートでなく総当りのループです。

正しくは
i=n-1～0,-1
j=0～i
で　(j)　と　(j+1）　を比べて逆転を入れ替えます。
これはバブルソート(隣接交換法）です。

No.3 回答者： ret 回答日時： 2003/09/08 10:26

こんなのでどうでしょうか?

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

typedef struct{
intnumber;
intresult;
}DATA;

//qsort用比較関数
int int_cmp( const void* _data1, const void* _data2 )
{
const DATA*cmp1 = (const DATA*)_data1;
const DATA* cmp2 = (const DATA*)_data2;
int sort;//両要素の差

sort = cmp2->result - cmp1->result;
if(sort != 0)return sort;
returncmp2->result - cmp1->result;
}


//main関数
int main(void){
DATA_data[10];
inti;
charbuf[256];

for(i = 0; i < 10; i++){
printf("学生番号を入力してください\n");
fgets(buf, 256, stdin);
_data[i].number = atoi(buf);

printf("成績を入力してください\n");
fgets(buf, 256, stdin);
_data[i].result = atoi(buf);
}

//sort
qsort( _data, sizeof(_data) / sizeof(DATA), sizeof(DATA), int_cmp );

for(i = 0; i < 10; i++){
printf("学生番号 = %d 成績 = %d\n", _data[i].number, _data[i].result);
}

(void)getchar();

return 0;
}

qsortを使っています。
検索エンジンでqsortとすると関数の詳細が出ますので、
解説はそれをご参考に…。
ただこれって構造体を扱うので、
10個程度なら問題ないのですが、
1万とか大きな数になると問題が大きいのですよね…(^^;。
構造体の交換に時間がかかってしまいますので…。
本当は各要素のポインタの配列をもう一つ用意して、
構造体ではなくそのポインタをソートすればいいのですが、
複雑になるのでやめました。
勉強をするなら、そちらも学ばれたほうが
後々役に立ちますよ(^0^)/

この回答への補足

わざわざ解答していただきありがとうございます.しかし、複雑過ぎてよく分かりません。僕の考えているプログラムを載せておきます。

include<stdio.h>
void main(void){
int d[100],c[100],n,a[100],i,j,x,max;
printf("n:");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&a[i],&d[i]); }
printf("ソート前データ\n");
printf("番号　音楽\n");
for(i=0;i<n;i++) printf("%d %2d\n",a[i],d[i]);
for(i=0;i<n-1;i++){
max=i;
for(j=i+1;j<n;j++)
if(d[max]<d[j]) {max=j; }
x=d[i]; d[i]=d[max]; d[max]=x;
}
printf("\nソート後データ\n");
printf("番号　音楽\n");
for(i=0;i<n;i++){
printf(" %2d\n",d[i]);
}
}

このプログラムを少しだけ修正（番号の出力）すればうまくいくと思っています。すいませんが他の方もこのプログラムにあった解法をしてくれればうれしいのですが・・・。

補足日時：2003/09/08 19:14

No.2 回答者： neue_reich 回答日時： 2003/09/08 08:58

調べる方針を書いてみますので参考にしてください。

まず、学生番号と点数を２次元配列に格納して扱います。
（ここでは配列名をＡをします）
Ａ１１＝１（学生番号）　Ａ１２＝５６（点数）
Ａ２１＝２　Ａ２２＝４７
Ａ３１＝３　Ａ３２＝８５
……

そして、その二次元配列の一つ目の添え字（Ａ２１なら２の方の添え字）
だけを考えて、ソートアルゴリズムを使用します。
アルゴリズムはバブルソートでもクイックソートでも
ヒープソートでもかまいません。
（これはプログラミング関係の入門書をみれば
どれかが載っています）
入れ替えのときに、学生番号の方の一つ目の添え字だけでなく、
点数の方の一つ目の添え字も入れ替えるのを忘れないように
してやれば完成です。

No.1 回答者： paspas 回答日時： 2003/09/08 08:56

ソートアルゴリズムもいろいろありますが、単純な物でよければ次のようにすればいかがでしょう。

データをd(n,2)に読み込みます。
d(n,0)が番号、d(n,1)が音楽の点数とします。

i,jをループ用変数とし
i=0～n-1　　nはデータ行数
j=i+1～n

比較式で d(i,1)とd(j,1)を比較しd(j,1)の方が大きければ d(i,1)とd(j,1),d(i,0)とd(j,0)をそれぞれ入れ替える。
ループが終われば順番に並んでいるはずです。