C言語関係掲示板

過去ログ

No.1331 qsortのcmp関数について

[戻る] [ホームページ]
No.17926

cmp関数について
投稿者---教えてください。(2004/11/10 02:11:14)


C言語の標準ライブラリに含まれているqsort()関数についてお聞きしたいことがあります。この関数の仕様の中で定義されているユーザ定義による比較関数として

int (* cmp)(const void *elem1, const void *elem2)

があると思うのですが、その返り値が

return(*(int *)arg1-*(int *)arg2));

となっている理由がわかりません。2つの項目を比較してその大小によって負、0、正のいずれかを返すという意味はわかるのですが、ここでのポインタ(*)の使われ方がわからないのです。どなたか教えていただけないでしょうか?



No.17927

Re:cmp関数について
投稿者---kolona(2004/11/10 02:34:38)


>int (* cmp)(const void *elem1, const void *elem2)
>
(int *)でint型ポインタにキャストして,
キャストしたポインタで値を参照して、計算しているのではないでしょうか。
qsortの第三引数に型の指定があるようなので、ここでint型を指定しておけば、
qsort関数からint型ポインタを引数として自作関数cmpを呼び出し、
自作関数cmpで実際にint型として計算しているのだと思います。

質問の意味を勘違いしてたらごめんなさい。


No.17952

Re:cmp関数について
投稿者---RAPT(2004/11/11 01:05:32)


qsortの第三引数に型の指定があるようなので、ここでint型を指定しておけば、
違います。
qsort()の第三引数はソートする配列の型ではなく、ソートする配列の要素のサイズ(バイト数)です。
qsort()の第二引数・第三引数は第一引数の情報となります。
また、第一引数の各要素が、第四引数の比較関数呼び出し時の引数になります。

例えば、qsort(array, num, width, compare); とあったとき、
compare(array[0], array[1]); のように呼び出されます。

あまり詳しく書くと、それこそクイックソートの実装になるので
詳細は省きますが、qsort()のプロトタイプは下記のとおりです。
void qsort( void *base, size_t num, size_t width, int (*compare)(const void *elem1, const void *elem2) );
base
ソートする配列の先頭
num
配列の要素数
width
配列要素のサイズ (バイト数)
compare
比較関数
elem1
検索キーへのポインタ
elem2
キーと比較される配列要素へのポインタ

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

#define countof(array) (sizeof(array)/sizeof(array[0]))

int cmp(const void *elem1, const void *elem2)
{
    const int *p_elem1 = (const int *)elem1;
    const int *p_elem2 = (const int *)elem2;
    const int n_elem1 = *p_elem1;    // *(const int *)elem1 と同等
    const int n_elem2 = *p_elem2;    // *(const int *)elem2 と同等

    if( n_elem1 > n_elem2 ){         // n_elem1 - n_elem2 は正
        return 1;
    }else if( n_elem1 == n_elem2 ){  // n_elem1 - n_elem2 は零
        return 0;
    }else{ // n_elem1 < n_elem2      // n_elem1 - n_elem2 は負
        return -1;
    }
    // return (*(const int *)elem1 - *(const int *)elem2); と1行で書くのと上記は同等
}

int main()
{
    int i, a[] = { 1,6,9,4,5,2,7,3,8 };

    puts("ソート前");
    for(i = 0; i < countof(a); ++i){
        printf("%d ", a[i]);
    }

    qsort(a, countof(a), sizeof(a[0]), cmp);

    puts("\nソート後");
    for(i = 0; i < countof(a); ++i){
        printf("%d ", a[i]);
    }

    return 0;
}

-----実行例-----
ソート前
1 6 9 4 5 2 7 3 8
ソート後
1 2 3 4 5 6 7 8 9



No.17954

Re:cmp関数について
投稿者---kolona(2004/11/11 03:11:45)


qsort()の第三引数はソートする配列の型ではなく、ソートする配列の要素のサイズ(バイト数)です。
すいませんそうでした。
指摘されて参考書を読み直してみると
width : 要素の大きさ
と明記されておりました。

・・・・と私が納得してもしょうがないですが。


No.18007

Re:cmp関数について
投稿者---RAPT(2004/11/11 20:31:04)


// return (*(const int *)elem1 - *(const int *)elem2); と1行で書くのと上記は同等
下記のとおり訂正します。
// return (*(const int *)elem1 - *(const int *)elem2); と1行で書くのと上記はqsort()の比較関数として使用する限り同等