qsortと動的確保の２次元配列

C言語で以下のようなソートのあるプログラムを作ろうとしているのですが、良い方法が思いつきません。。。。
どなたか,知恵を貸していただけないでしょうか？

・複数人の身長と体重がcsvファイルに2列に入っている。

人 身長 体重
1 158.9 50.5
2 161.2 72.3
3 150.4 42.8
4 170.7 80.4
5 165.0 59.9
・ ・
・ ・
・ ・


・↑このように身長も体重もランダムに並んでいる状態

・身長・体重をプログラムで読み込んだら 身長の低い順にソートする。この時体重も身長に対応して並び換わってほしい。
(わかりやすいかと思い人の番号列を設けましたが、人の番号は考えなくて良いです)


この問題に対して,データ数が不特定かつ多いため
動的確保の2次元配列を使ったクイックソートで対応を考えます。

qsortについてあれこれ調べていたのですが,動的確保でのqsort例が無く困っています。。。

どなたかちょっとアドバイスをいただけないでしょうか？
よろしくお願いします。






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

enum {HIGHT, WEIGHT, COLUMN};

int comp (const void *a, const void *b) //比較関数
{
return (int) (((double *)a)[HIGHT] - ((double *)b)[HIGHT]) ;
}



int main(void)
{

//////////////////////////////////////////////////////////
私情により、ソート以前の処理で使用するため
あらかじめ .csv ファイルから fget で値を読み込んで　コンマで分割しx[]y[]に格納してある。

＆データ数をカウントしている

今は省略　


仮定として以下のように５つのデータ数を読み込んでいたとする

double x[5] = {158.9,161.2,150.4,170.7,165.0};
double y[5] = {50.5,72.30,42.8,80.4,59.9};

int n=5; //データカウント数

///////////////////////////////////////////////////////////

int i;
double **list;

list = (double**)malloc(sizeof(double)*5);

for (i=0 ; i< 5 ; i++)
{
list[i] = (double*)malloc(sizeof(double)*COLUMN);
if (list[i]==NULL) return 1;/* 領域確保に失敗したか */

}

for(i=0;i<n;i++)
{
list[i][HIGHT]=x[i];
list[i][WEIGHT]=y[i];
}

for(i = 0; i < n; i ++) printf("%lf %lf\n", list[i][HIGHT], list[i][WEIGHT]);

puts("Sort");
qsort(list,n, sizeof(double [COLUMN]), comp);

for(i = 0; i <n; i ++) printf("%lf %lf\n", list[i][HIGHT], list[i][WEIGHT]);

scanf("%d",i);
return 0;


}

No.6 回答者： chie65535 回答日時： 2008/12/19 17:26

追記の追記の追記。

「単純な構造体にして、構造体の配列を、qsortにソートさせる」と言う方が、ずっと簡単で、メモリの確保や解放も１回で済みます。

しかし「データ件数が膨大になる」と「qsortが、構造体要素を入れ替えする時間」が無視出来なくなります。

doubleの要素が２つある構造体配列だと、最低でも１要素は１６バイトです。

qsortは、入れ替えが必要になるたびに「１６バイトを入れ替え」します。

なので（そう書くつもりじゃなかったとしても、偶然の結果）質問者さんが書いたような「ポインタが並んでるリスト構造」にして「qsortが入れ替えるのは、リストの中のポインタだけ」にすれば、入れ替えは「ポインタのサイズ（つまり、４バイト）」だけで済みます。

例えば、データ項目が「double 2つ」ではなく「double 2つと、datetime型の日付と、長さ256バイトの氏名」だったとします。

qsortに「構造体をそのまま入れ替えさせる」と「１件並び替え」するごとに、なんと、300バイト近くのデータを入れ替えます。

もし、件数が1000件あったら…。

リストの中のポインタだけqsortに並び替えさせれば、構造体の大きさが300バイトだろうが、3000バイトだろうが、入れ替えるのは４バイトです。

ただ、リスト構造にすると「メモリの確保と解放の処理が面倒」になりますので、それが欠点です。

この回答へのお礼

丁寧に教えてくださって本当にありがとうございます！
無事に動くようになりました。
初心者なりにいろいろ調べてみたものの,いろいろ途中と半端な状態でお願いてしまってお恥ずかしいです；

非常に勉強になりました。ありがとうございました！！　(> <

お礼日時：2008/12/19 20:38

No.5 回答者： Tacosan 回答日時： 2008/12/19 17:12

どうでもいいところですが,

list = (double**)malloc(sizeof(double)*5);
って意味的には間違ってますよね. 個人的には
list = (double**)malloc(sizeof(list[0])*5);
のような形の方が好み.
あと, 将来のことを考えるとデータの持ち方を考えた方がいいかもしれない. 「線形リストでもってマージソート」というのも選択肢に挙げておいたほうが良いと思います.

この回答へのお礼

ご指摘ありがとうございます！

”線形リストでもってマージソート”　ですか
マージソートはなんとなくわかりますが
線形リストはノードを自由に増やせるとかって事くらいしかわからないのが現状です；；

これをきに勉強してみたいと思います♪

お礼日時：2008/12/19 23:28

No.4 回答者： chie65535 回答日時： 2008/12/19 17:09

追記の追記。

動的に確保したメモリは、使い終わったら解放しましょう。

return 0;
↓
for (i=0 ; i< 5 ; i++)
{
if (list[i]!=NULL) free(list[i]);
}
free(list);
return 0;

また、listの確保に失敗した時や、list[i]を途中まで確保して失敗した時は、解放してからreturnしましょう。

int i;
↓
int i,j;

list = (double**)malloc(sizeof(double)*5);
↓
list = (double**)malloc(sizeof(double *)*5); /*さっき、ここ、見落とし*/
if (list==NULL) return 1;/* 領域確保に失敗した */

if (list[i]==NULL) return 1;/* 領域確保に失敗した */
↓
if (list[i]==NULL) {
for(j=i-1;j >= 0;j--) if (list[j]!=NULL) free(list[j]); /* 途中まで確保したのを解放 */
free(list);
return 1;/* 領域確保に失敗した */
}

何度も何度も繰り返し実行していると、メモリリークが発生するので「mallocしたら必ずfree」を徹底しましょう。

No.3 回答者： chie65535 回答日時： 2008/12/19 16:51

すいません、嘘書きました。

＞そこさえ直せば「取りあえず、現状のままでも動く」と思います。

動きません。

list配列の構造と、qsortに渡すパラメータが一致してません。

このプログラムはメモリを破壊し、最悪、例外を出力して落ちます。

listの示すポインタのメモリには「doubleへのポインタが５つ並んでるだけ」です。

普通に
list[i][HIGHT]=x[i];
list[i][WEIGHT]=y[i];
として、まるで２次元配列のようにアクセス出来てしまうので、２次元配列と勘違いしてしまいがちですが「実体は全然違う」のです。

そして、comp関数には、&list[0]や&list[1]が、つまり「double **」が渡されてきます。

comp関数の中で
return (int) (((double *)a)[HIGHT] - ((double *)b)[HIGHT]) ;
と評価すると、double **の場所を、double *[HIGHT]としてアクセスするので、訳の判らない評価をします。

しかも、qsortは、要素の大きさが「sizeof(double [COLUMN])」だと思って、listの要素を入れ替えしようとします。

しかし、listには「doubleへのポインタが５つ並んでるだけ」なので、訳の判らないメモリを訳も判らずに並び替えします。

そして、不正なメモリにアクセスし、例外を発生して落ちます。

以下の３点を変更すれば、こんどこそ、正常に動きます。

return (int) (((double *)a)[HIGHT] - ((double *)b)[HIGHT]) ;
↓
return (int) (((*(double **)a)[HIGHT] - (*(double **)b)[HIGHT])*10) ;

qsort(list,n, sizeof(double [COLUMN]), comp);
↓
qsort(list,n, sizeof(double *), comp);

scanf("%d",i);
↓
scanf("%d",&i);

No.2 回答者： chie65535 回答日時： 2008/12/19 16:24

comp関数の

＞return (int) (((double *)a)[HIGHT] - ((double *)b)[HIGHT]) ;
はバグってる。

「身長差が0.2の時、intにキャストしたらどうなるか？」を考えてみよう。

「両方を１０倍してから引き算してintにする」とか「引き算した結果を１０倍してからintにする」とか「if文を使う」とか「３項演算子を使う」とかしないと、ちゃんとソートされません。

そこさえ直せば「取りあえず、現状のままでも動く」と思います。

No.1 回答者： Yanch 回答日時： 2008/12/19 14:16

1行分のレコードを一件のデータとして扱えるように、

構造体を用意すると良いと思います。