qsortについて

qsort()で構造体をソートする時に、qsortの第3,4引数時の、「size t_t size, int (*cmp)(const void *a, const void *b)」の使い方が分かりません。
何故これを使ってソートが出来るのでしょうか？そもそも、構造体を送った時に、自作関数内での書き方にも疑問があります。

int main(void){
MAX dt[5]={・・・・}; //構造体変数宣言
・・・・・
qsort(dt,5,sizeof(MAX),sum); //(*1)
....
return 0;
}

int sum(const void *a, const void *b){
MAX *p1 = (MAX *)a; //(*2)
MAX *p2 = (MAX *)b; //(*2)
・・・・
return ～;
}

----------------------------------------------------
*1: 第3引数のsizeof(MAX)って何ですか？
*2: 例えばint型が渡されてreturnする場合は、「return *(int *)a - *(int *)b 」でいいのに、
　　何故構造体の場合はこう書かないといけないのですか？

No.4 ベストアンサー 回答者： Oh-Orange 回答日時： 2007/07/27 18:29

★qsort() 関数について

・関数のプロトタイプ宣言は
　void qsort( void *base, size_t num, size_t size, int (*comp)(const void*, const void*) );
　です。
　第１引数(base)…base という配列の先頭ポインタを渡す
　第２引数(num)…base という配列の要素数を渡す
　第３引数(size)…base という配列の１つの要素のバイト数を渡す
　第４引数(comp)…ユーザ定義の比較関数を渡す
　となります。
・この関数は int型、long型、double型、構造体などのどんな型の配列でも扱えるように
　工夫されています。そしてこの工夫から第３引数の size や第４引数の comp という
　ユーザ定義の比較関数を引数で受け取っているのです。
・もし int 型専用のソート関数を自作すると base という配列の先頭ポインタとその要素数
　の２つだけを引数に渡せばいいことになります。そして自作のソート関数では内部できっと
　比較関数にあたる『比較処理』を実装することになります。一番簡単なバブルソートを
　思い出して下さい。比較処理する部分がありますよね。この部分を関数にして分離することで
　昇順、降順とかそれ以外のソート条件にも関数を入れ替えるだけで対応できるのです。
・qsort() 関数は汎用性が高くなるように工夫されています。そのため第４引数に比較関数を
　受け取る(渡す)仕様になっているのです。また、自作関数では base という配列に型を指定
　するため size は必要ありませんがどんな型の配列でも使えるようにするには１つの要素の
　サイズの情報が必要になります。例えば int型の配列なら sizeof(int) のサイズがね。
　このように qsort() では内部で使う情報として size、comp 関数を第３引数と第４引数で
　受け取るわけです。

本題:
＞*1: 第3引数のsizeof(MAX)って何ですか？
　↑
　これは MAX という構造体データの１つ分のバイトサイズです。
　もし int型の配列をソートする場合は sizeof(int) となります。
　１つ分の型のサイズです。単純変数(int、long、doubleなど)でも構造体の場合でも同じ。
＞*2: 例えばint型が渡されてreturnする場合は、「return *(int *)a - *(int *)b 」でいいのに、
＞　　何故構造体の場合はこう書かないといけないのですか？
　↑
　それは構造体名がポインタを表しているだけでデータの『値』を表していないためです。
　でも構造体でも似たようなことは出来ますけど。
・例えば
　typedef struct max_t {
　　int a;
　　char b;
　　char *c;
　} MAX;
　の場合で int a でソートする比較関数は
　int comp( const void *d1, const void *d2 )
　{
　　return ((MAX*)d1)->a - ((MAX*)d2)->a;
　}
　と出来ます。また char *c でソートする場合は
　int comp( const void *d1, const void *d2 )
　{
　　return strcmp( ((MAX*)d1)->c, ((MAX*)d2)->c );
　}
　と出来ます。
　※正しくは比較演算子(< = >)を使いましょう。sakusaker7 さんより。
＞MAX *p1 = (MAX *)a; //(*2)
＞MAX *p2 = (MAX *)b; //(*2)
　↑
　これはソースを分かり易くする為に p1 と p2 に代入しているのです。
　キャストすれば構造体でも出来ますが複雑な条件でソートをする場合は見づらいです。
・例えば上記の構造体の a でソートして同じ場合は c でソートする２段階のソートでは
　int comp( const void *d1, const void *d2 )
　{
　　if ( ((MAX*)d1)->a < ((MAX*)d2)->a ) return -1;
　　if ( ((MAX*)d1)->a > ((MAX*)d2)->a ) return +1;
　　return strcmp( ((MAX*)d1)->c, ((MAX*)d2)->c );
　}
　とします。
　『((MAX*)d1)』というキャストが６箇所あります。
・これを p1 と p2 に代入すると
　int comp( const void *d1, const void *d2 )
　{
　　MAX *p1 = (MAX*)d1;
　　MAX *p2 = (MAX*)d2;
　　
　　if ( p1->a < p2->a ) return -1;
　　if ( p1->a > p2->a ) return +1;
　　return strcmp( p1->c, p2->c );
　}
　と見やすくなるでしょう。だから構造体の場合は代入したりもします。
　それだけ。最終的には個人の自由ですが可読性、保持性などいろいろ考えて代入をお勧め。
・以上。

参考URL：http://www.cc.kyoto-su.ac.jp/~yamada/ap/qsort.html

No.3 回答者： sakusaker7 回答日時： 2007/07/27 02:47

> returnする場合は、「return *(int *)a - *(int *)b 」でいいのに、

INT_MINが絡むと悲しい結果になるので、この式は使わないほうが良いです。

No.2 回答者： php504 回答日時： 2007/07/26 19:54

qsortの第4引数は2個のポインタを引数として使いintを戻り値とする比較関数へのポインタを示します。

つまり比較用の自作関数は
int cmp(const void *a, const void *b){}
のような宣言になります。
比較関数がするべきことは2個の引数を比較して正の整数か0か負の整数を返すことです。
*a, *bが整数であれば昇順にソートする場合は単純に *a - *bを返せばこの条件が満たせます。
ただ引数がvoid型であるため元の型にキャストしなければなりません。
つまり
int *a1 = (int*)a;
int *b1 = (int*)b;
return *a1 - *b1;
のようになります。これを1行にまとめたのが
return *(int *)a - *(int *)b;
になります。
構造体の場合もvoid型を構造体の型にキャストして比較しないといけないので。
MAX *p1 = (MAX *)a;
MAX *p2 = (MAX *)b;
// のように一旦キャストして
return p1->member - p2->member;
メンバ変数にアクセスする必要があります。

No.1 回答者： maku_x 回答日時： 2007/07/26 17:21

こちらの疑問ですが、

> 何故これを使ってソートが出来るのでしょうか？
そのように qsort() 関数がプログラムされているからです。
> *1: 第3引数のsizeof(MAX)って何ですか？
qsort() から呼び出される比較関数に渡される変数1個当たりのサイズです。これが分からないと、qsort() 関数は正しく並び替えすることができません。
> *2: 例えばint型が渡されてreturnする場合は、「return *(int *)a - *(int *)b 」でいいのに、何故構造体の場合はこう書かないといけないのですか？
qsort() から呼び出される比較関数は、「第一の引数が第二の引数に対 して、1)小さい、2)等しい、3)大きいならば、1)ゼロ未満、2)ゼロ、3)ゼロより大きい整数のいずれかを返さなければならない。」なので、int 型を昇順に並び替える場合は、そのように書けば、この条件を満たします。構造体の場合は、そのままでは大小比較できませんから(もっとも、return memcmp(a,b,sizeof(MAX)) と書けば構造体の中身のバイナリ値で比較することはできますが)、基本的には構造体のメンバ変数で比較する必要があります。