構造体配列の安定なソート

出席番号と得点の配列を持つ構造体配列で、
出席番号順に並んだ状態でqsortを使って得点をソートする場合、
同じ得点の人でも、出席番号順はばらばらになってしまいますよね。

調べてみて、バブルソートなど安定なソートを使えばいいということが分かったのですが、
qsortは標準ライブラリにあって、
比較関数も見よう見まねで作ってなんとかなったのですが、
他の方法となると具体的にどうすればいいのか、
よくわからない状況です。

http://homepage1.nifty.com/daccho/program/algo/s …

こちらのサイトのソースファイルを見て、
普通のint配列のバブルソートは出来たのですが、
構造体配列を、構造体の中の一つの要素をキーにバブルソートできるようにするには、
ここからどのように変更すればいいのでしょうか？

並び替える内容はint型だけなので、文字列をソートできるようにする必要はなく、
ソート対象も少ないので（上限100程度）、速度的な問題は考慮しなくて大丈夫だと思います。

Cは勉強中で、基本文法がわかるぐらいという状況で、
もしかしたら変なことを言っているのかもしれませんが、
よろしくお願いします。

No.4 ベストアンサー 回答者： BLUEPIXY 回答日時： 2006/05/14 21:48

>構造体のメンバを引数に渡すにはどうすればいいかとか、

>bubble_sort(&table[0].score, 10);
bubble_sort(&table[0], 10)
とすればいいと思います。
＞メンバの配列を比較してメンバの順番だけ入れ替えたら、
＞名前と得点の対応が壊れるから、
構造体自体は、出席番号と得点を保持しているのだから、
出席番号から名前が引き出せるのであれば、対応をとる必要はないと思うのですが、構造体の配列の並びがどっか別にある名前テーブル(配列？)と対応しているということであれば、名前テーブルも並び替える必要があるのかなぁとか思いますが、そんな必要はないような気がします。
なんか、どういうデータ構造になっているかよくわからないので、勘違いしてたらすみませんです。
できたら、バブルソート版のプログラムを補足していただけますか?

この回答への補足

ありがとうございます。

＞bubble_sort(&table[0], 10)
＞とすればいいと思います。

渡すのは構造体で、関数内でメンバにアクセスするということですか。qsortでもそうでした。
これだと関数を書き換えないと駄目ですよね。

バブルソート版のプログラムは、
http://homepage1.nifty.com/daccho/program/algo/s …
です。

void swap(int *ptr1, int *ptr2)
{
int w;

w = *ptr1;
*ptr1 = *ptr2;
*ptr2 = w;
}

void bubble_sort(struct scoretable *ptr, int n)
{
int i, j;

for(i=0; i<n-1; i++){
for(j=n-1; j>i; j--){
if(*((ptr->score)+j-1) > *((ptr->score)+j)){
swap(((ptr->score)+j-1), ((ptr->score)+j));
}
}
}
}

bubble_sort()の引数の型を書き換えて、
メンバにアロー演算子でアクセスするようにしただけで、
間接指定演算子 (*) の使い方が不正です。
'swap' : 1 番目の引数を 'int' から 'int *' に変換できません。
などのエラーが出ています。

ポインタを理解していない状態なので、多分今は理解しようとしても理解できないと思います。
それは後で本を読んで勉強するとして、
とりあえず今は動くようになればいいのですが。

構造体は普通の構造体で、メンバとして出席番号と得点があるで
問題ないです。対応が壊れるというのは、構造体の仕組みを勘違いしていました。

補足日時：2006/05/14 22:25

この回答へのお礼

アドバイスが役に立ちなんとかできました。
ありがとうございました。

void swap(struct scoretable *ptr1, struct scoretable *ptr2)
{
struct scoretable w;

w = *ptr1;
*ptr1 = *ptr2;
*ptr2 = w;
}

void bubble_sort(struct scoretable *ptr, int n)
{
int i, j;

for(i=0; i<n-1; i++)
{
for(j=n-1; j>i; j--)
{
if(ptr[j-1].score > ptr[j].score)
{
swap(&ptr[j-1], &ptr[j]);
}
}
}
}

お礼日時：2006/05/15 02:50

No.3 回答者： moritan2 回答日時： 2006/05/14 20:44

単純ミスじゃないでしょうか？

if((u->score - u->score)!=0)

これは

if((u->score - v->score)!=0)

でしょう？

この回答へのお礼

そこは間違いでした。
ありがとうございます。

ただやはりこの方法だとできないみたいです。

お礼日時：2006/05/14 21:25

No.2 回答者： BLUEPIXY 回答日時： 2006/05/14 17:55

>int配列のバブルソートは出来た

のであれば、
比較する値を構造体のメンバの得点にして、
交換するのを構造体（値型だから）にするか、それぞれの、メンバを交換すればいいだけです。

この回答への補足

すいませんが、
具体的にどのように変更すればいいのかが
わからない状態です。

構造体のメンバを引数に渡すにはどうすればいいかとか、
bubble_sort(&table[0].score, 10);
配列の先頭要素を渡すということはこういうことなのか、それともこうなのか。
bubble_sort(&table[i].score, 10);

関数側のほうにも修正が必要なのかとか。

メンバの配列を比較してメンバの順番だけ入れ替えたら、
名前と得点の対応が壊れるから、
そうすると、最初に構造体のメンバだけでなく、
構造体配列そのものも渡して、関数の中でどうにかするということなんでしょうか。
そうするとやはり元の関数自体も変更する必要がありますよね。

補足日時：2006/05/14 18:17

No.1 回答者： a-saitoh 回答日時： 2006/05/14 17:55

比較関数を，「得点を比較するが，得点が同じで場合は出席番号で代償をきめる」というものにすれば，クイックソートでも大丈夫では?

この回答への補足

ありがとうございます。
元々の、比較関数は

int _cdecl cmp(const void *a, const void *b)
{
struct scoretable *u, *v;
u = (struct scoretable *)a;
v = (struct scoretable *)b;
return u->score - v->score;
}

のようになってるんですが、これを、

int _cdecl cmp(const void *a, const void *b)
{
struct scoretable *u, *v;
u = (struct scoretable *)a;
v = (struct scoretable *)b;

if((u->score - u->score)!=0)
{
return u->score - v->score;
}
else
{
return u->no - v->no;
}

}

のようにかえたのでは駄目でした。
多分これでは間違いなのだと思うのですが、
具体的にどのように変えればいいのでしょうか。

補足日時：2006/05/14 18:41