みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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

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[]に格納してある。

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

今は省略 


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

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;


}

投稿日時 - 2008-12-19 13:03:00

QNo.4567626

すぐに回答ほしいです

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(6)

ANo.6

追記の追記の追記。

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

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

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

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

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

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

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

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

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

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

投稿日時 - 2008-12-19 17:26:32

お礼

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

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

投稿日時 - 2008-12-19 20:38:51

ANo.5

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

投稿日時 - 2008-12-19 17:12:41

お礼

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

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

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

投稿日時 - 2008-12-19 23:28:03

ANo.4

追記の追記。

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

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」を徹底しましょう。

投稿日時 - 2008-12-19 17:09:49

ANo.3

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

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

動きません。

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

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

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

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

そして、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へのポインタが5つ並んでるだけ」なので、訳の判らないメモリを訳も判らずに並び替えします。

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

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

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);

投稿日時 - 2008-12-19 16:51:09

ANo.2

comp関数の
>return (int) (((double *)a)[HIGHT] - ((double *)b)[HIGHT]) ;
はバグってる。

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

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

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

投稿日時 - 2008-12-19 16:24:36

ANo.1

1行分のレコードを一件のデータとして扱えるように、
構造体を用意すると良いと思います。

投稿日時 - 2008-12-19 14:16:45

あなたにオススメの質問