C言語関係掲示板

過去ログ

No.1116 実数値のデータをソートしたいです。qsortは使えませんか?

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

実数値のデータをソートしたいです。qsortは使えませんか?
投稿者---ピヨピヨ(2004/06/01 14:02:47)


初めまして。
実数値のデータをソートしたいです。昇順・降順は問いません。
調べたところqsortが使えるかもと思い、いろいろなプログラムを例に
作ってみました。整数値だとうまく結果がでますが、
実数値だとうまくいきません。配列をdouble型にかえるなどしてみましたが、だめでした。
作ってみたプログラムを以下に載せました。整数値でうまくいくプログラムです。
恐れ入りますが教えていただけませんでしょうか。

なお、最終的にはファイルに書かれたデータ(実数値)から構造体の型で読み取り、ソートするつもりでいます。ですので作りかけではありますがプログラムの該当箇所はコメント文にしています。
よろしくお願いいたします。

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

int compare( const void *a, const void *b);

int main(void){

/*
     FILE *fp1,*fp2;
 
 if( ( fp1 = fopen("in.log","r") ) == NULL) 
 { 
  printf("in.log is not here.\n"); 
  return 0; 
 } 
 if( ( fp2 = fopen("out.log","w") ) == NULL) 
 { 
  printf("out.log is not here. \n"); 
  return 0; 
 } 
   
   fp1 = fopen("in.log","r");   
   printf("read from in.log \n"); 
   
   fp2 = fopen("out.log","w");
   printf("stand by out file \n"); 
*/

    int obj[10]= {10,3,6,4,2,9,1,5,7,8};
    int *swap[10];
    int i=0;
/*
while(EOF != fscanf(fp1,"%lf\n",&obj[i]) )// 
{
    printf("%lf\n",obj[i]);
    i++;
}
*/
    for(i = 0; i<10; i++){
         swap[i] = &obj[i];
    }

    printf("ソート前\n");
    for(i = 0; i<10; i++){
        printf("%d ", *swap[i]);
    }

    qsort(&swap[0], 10, sizeof(int *), compare);

    printf("ソート後\n");
    for(i = 0; i<10; i++){
        printf("%d ", *swap[i]);
    }
    return 0;
}

int compare( const void *a, const void *b)
{
    return( ** (int **) a -  ** (int **) b);
}




No.1867

Re:実数値のデータをソートしたいです。qsortは使えませんか?
投稿者---ピヨピヨ(2004/06/01 14:07:10)


すみません。環境が抜けておりました。
VC++6.0を使っています。
よろしくお願いいたします。


No.1868

Re:実数値のデータをソートしたいです。qsortは使えませんか?
投稿者---nop(2004/06/01 14:19:50)


>実数値のデータをソートしたいです。昇順・降順は問いません。

深くテストしてないが、
おおよそこんな感じで。


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


int compare( const void *area1, const void *area2 )
{
    const double *value1 = (const double *)area1;
    const double *value2 = (const double *)area2;
    int           ret = 0;

    /* ----- 比較処理 ----- */
    if( *value1<*value2 )
    {
        ret = -1;
    }
    if( *value1>*value2 )
    {
        ret = 1;
    }
    return ret;
}


int  main( void )
{
    /* ----- 内部変数定義 ----- */
    double  values[] = { 1.0, 5.2, 3.45, 0.002, 12.58, 4.23, 89.65, 0.25, 20.11 };
    int     i;

    /* ----- ソート前のデータを表示 ----- */
    puts( "ソート前のデータを表示" );
    for( i=0; i<sizeof(values)/sizeof(values[0]); i++ )
    {
        printf( "values[%d] = %f\n", i, values[i] );
    }
    /* ----- データのソート ----- */
    qsort( values, sizeof(values)/sizeof(values[0]), sizeof(values[0]), compare );

    /* ----- ソート後のデータを表示 ----- */
    puts( "ソート後のデータを表示" );
    for( i=0; i<sizeof(values)/sizeof(values[0]); i++ )
    {
        printf( "values[%d] = %f\n", i, values[i] );
    }
    return 0;
}



No.1869

早速のご返答ありがとうございます。
投稿者---ピヨピヨ(2004/06/01 14:41:45)


お世話になります。
nop殿 早速のご返答ありがとうございます。
今プログラムを実行しましたところ正確にソートができておりました。
本当にありがとうございます。

nop殿のプログラムと私のプログラムとを比較し、なぜ
私のプログラムがうまく動かなかったのか検討してみます。
まだまだ勉強不足ですが今晩考えてみます。
(qsortの第3パラメータなのかなぁ…)

急ぎお礼をお伝えしたく投稿しました。


No.1870

Re:早速のご返答ありがとうございます。
投稿者---nop(2004/06/01 15:27:49)


>私のプログラムがうまく動かなかったのか検討してみます。
>まだまだ勉強不足ですが今晩考えてみます。
>(qsortの第3パラメータなのかなぁ…)

qsort()の引数もそうですが、
比較関数の書き方が間違っています。

比較関数は、qsort()内部で要素の比較がある時に呼ばれます。
その際、比較する二つの要素の領域の先頭ポインタ値を引数として渡します。
比較関数内では、このポインタを適切な型にキャストで当てはめ、
二つの要素の比較結果を返します。

比較の仕方は、「qsort()にどんな配列を渡すか?」や、
「並び順は昇順か?それとも降順か?」などによって変わりますが、
二つの要素が等しい場合には0を、
第一引数の要素が、第二引数の要素より小さい場合には負数、
第一引数の要素が、第二引数の要素より大きい場合には整数を、
それぞれ返す事で qsort() でソートできるようになってます。


No.1873

qsort、比較関数を再度理解しなければいけませんね。ありがとうございます。
投稿者---ピヨピヨ(2004/06/01 21:05:41)


>qsort()の引数もそうですが、
>比較関数の書き方が間違っています。
ご指摘ありがとうございます。
qsortのパラメータについては本やHP等に載ってあるので
適宜パラメータ等変えていけばいいと思っていましたが
理解が不足していました。

さっそくファイルから読み取れるようにして、
次に構造体で格納したデータをソートできるようにしてみます。
ご協力ありがとうございました。


No.1875

ひとつ疑問があります。データ数があらかじめわからないときは配列の宣言ができませんか?
投稿者---ピヨピヨ(2004/06/01 22:58:45)


ファイルからデータ(実数値)を読み取り、そのデータをソートさせようとしています。ファイルにデータがいくつあるのかはあらかじめわからない状態です。この場合だとqsortにいれるサイズがあらかじめわかりません。どのようにすればよろしいでしょうか。

nop殿のプログラムでは
double values[] = { 1.0, 5.2, 3.45, 0.002, 12.58, 4.23, 89.65, 0.25, 20.11 };
とあらかじめ配列valuesのサイズがわかっておりqsortを使えますが

#define num 10000
double values[num];
int i=0;
・・・ファイルポインタ文等・・・
while(EOF != fscanf(fp1,"%lf\n",&values[i]) ){
i++;}//ファイルの終わりまでデータを取得する。
といった感じでファイルからデータを取り込む場合,最後のi++の数字がほしい配列のサイズになります。ですが実際はsizeof(values)はnumの数になってしまいます。
試しにqsortのsizeof(values)にiの値を入れてみましたがうまくいきませんでした。

ファイルからデータを取得した後にソートの対象数が分かります。
よいアイデアをよろしくお願いいたします。

【経緯】
とあるログファイルにデータが書かれてあります。
そのファイルからデータを読み取りソートしたいと思っています。
また、ファイルには余分なデータがあるので範囲を指定してソートする予定です。例えばログファイルには5月30日から6月2日まで1時間毎にデータがあります。6月1日分のデータだけを取り出してソートするといった感じです。


No.1876

Re:ひとつ疑問があります。データ数があらかじめわからないときは配列の宣言ができませんか?
投稿者---nop(2004/06/01 23:45:00)


>ファイルからデータ(実数値)を読み取り、そのデータをソートさせようとしています。
>ファイルにデータがいくつあるのかはあらかじめわからない状態です。
>この場合だとqsortにいれるサイズがあらかじめわかりません。

ファイルを取り込めば、ソートしたいデータの個数は求まるはずです。
その個数をqsort() の第二引数にそのまま指定すれば良いです。

>#define num 10000
>double values[num];
>sizeof(values)はnumの数になってしまいます。

sizeof演算子で得られるのは、配列の個数ではなくバイト数です。
従って、sizeof(values) の値は「num * sizeof(double)」になります。

>試しにqsortのsizeof(values)にiの値を入れてみましたがうまくいきませんでした。

変数「i」がデータの個数を示しているのなら、
「sizeof(values)」を「i」に変えるのではなく、
「sizeof(values)/sizeof(values[0])」を「i」に変えて下さい。
qsort()の第二引数で与える値は要素の数ですから。

それから、構造体配列のソートを行いたいようなので、
配列変数「values」を構造体配列に変えている場合には、
qsort()の第三引数にも注意して下さい。


以下に、構造体配列の場合のソートの例も載せておきます。

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

typedef struct
{
    char  Name[32];
    int   Value;
} strTestData;

int compare( const void *area1, const void *area2 )
{
    const strTestData *value1 = (const strTestData *)area1;
    const strTestData *value2 = (const strTestData *)area2;
    int                ret;

    /* ----- 比較処理 ----- */
    ret = value1->Value - value2->Value;

    if( ret==0 )
    {
        ret = strcmp( value1->Name, value2->Name );
    }
    return ret;
}

int  main( void )
{
    /* ----- 内部変数定義 ----- */
    strTestData  iData[1024] = {0};
    FILE        *iFp;
    char         iLine[512] = {0};
    int          iCount = 0;
    int          i;
    char        *p;

    /* ----------------------------------------
        ファイルからデータを読み込む
    ---------------------------------------- */
    iFp = fopen( "test.txt", "r" );

    if( iFp )
    {
        while( iCount<1024 && fgets(iLine,sizeof(iLine),iFp)!=NULL )
        {
            p = strtok( iLine, "=" );
            strncpy( iData[iCount].Name, p, sizeof(iData[iCount].Name) );
            p = strtok( NULL, "\n" );
            iData[iCount].Value = strtol( p, NULL, 10 );
            iCount++;
        }
        fclose( iFp );
    }
    /* ----------------------------------------
        ソート前のデータを表示
    ---------------------------------------- */
    printf( "ソート前データ (%d 個)\n", iCount );

    for( i=0; i<iCount; i++ )
    {
        printf( "%s : %d\n", iData[i].Name, iData[i].Value );
    }
    /* ----------------------------------------
        データをソート
    ---------------------------------------- */
    qsort( iData, iCount, sizeof(iData[0]), compare );

    /* ----------------------------------------
        ソート後のデータを表示
    ---------------------------------------- */
    printf( "\nソート後データ (%d 個)\n", iCount );

    for( i=0; i<iCount; i++ )
    {
        printf( "%s : %d\n", iData[i].Name, iData[i].Value );
    }
    return 0;
}

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
※「test.txt」と言うファイルを用意し、
 「名前=値」の形式で書かれたテキストを数行入れて下さい。

[test.txtの例]
test=10
data=1024
hoge=35
huge=564
foo=224
info=1
charsize=1
intsize=4
retrycount=15



No.1878

うまくいきました。ありがとうございます。
投稿者---ピヨピヨ(2004/06/02 01:21:00)


nop殿
>「sizeof(values)/sizeof(values[0])」を「i」に変えて下さい。
うまくいきました。ありがとうございます。

>ファイルを取り込めば、ソートしたいデータの個数は求まるはずです。
仰るとおりです。 while(EOF != fscanf(fp1,"%lf\n",&values[i]) )といった具合にファイルの終わりまでループを回しデータを取得しているのでこの最後のiが求めたい個数になります。

>sizeof演算子で得られるのは、配列の個数ではなくバイト数です。
ご指摘いただいた点を省みると結局私はqsortを理解できていなかったということですね。

>以下に、構造体配列の場合のソートの例も載せておきます。
お手数をおかけして申し訳ありません。感謝の気持ちでいっぱいです。
プログラムを実行したところ見事にソートされていました。

>配列変数「values」を構造体配列に変えている場合には、
>qsort()の第三引数にも注意して下さい。
第3引数は、並べ替える配列の要素1つの大きさであって、
sizeof(要素の型)を渡すということでよろしいでしょうか。
作っていただいた例で考えますと、
構造体strTestData型配列のひとつの要素(iData[0])の大きさを指定する
ということになりますでしょうか。

的確なポイントを教えていただきありがとうございます。


No.1885

折角書いていただいた例を理解したく存じます。調べてはいますが今ひとつ理解できておりません。
投稿者---ピヨピヨ(2004/06/02 16:09:40)


お世話になります。
ファイルに書かれた実数値を構造体で読み取りソートするプログラムを作っております。まず、nop殿に作っていただいた例を用いて実数値をソートするように作っております。
単に int Value;をdouble Value; とすると
ret = value1->Value - value2->Value;
でwarningがでます。retはint型なので当然です。強引にビルドして実行すると
結果はきちんとソートされますが納得いきません。

私が理解できていない点は率直に申しますと、
int compare( const void *area1, const void *area2 )
{
const strTestData *value1 = (const strTestData *)area1;
const strTestData *value2 = (const strTestData *)area2;
int ret;

/* ----- 比較処理 ----- */
ret = value1->Value - value2->Value;
の部分です。

部分的に理解できている点は、
・const は変数の内容を変更できないことを表す。
・この例の場合ポインタ*area1、*area2の値を変更できないことを意味している。
・value1->Nameについてはポインタ変数value1を用いてstrTestData型のValue
のデータ(iData[i].Valueのデータ)を参照している。
・compareは比較関数であること。初めにnop殿からご指摘を受けました。

nop殿に作っていただいた例を理解すべくまた、
warningがでないようにするにはどうすればいいのかいろいろ調べております。
なお、私がもっている本は
プログラミング言語C「B.W.カーニハン (著),D.M.リッチー (著),石田 晴久」
今さら聞けないCの基礎「山岡 祥(著)」
です。

差し支えなければ恐れ入りますがご教授の程よろしくお願い致します。


No.1887

Re:折角書いていただいた例を理解したく存じます。調べてはいますが今ひとつ理解できておりません。
投稿者---nop(2004/06/02 17:08:17)


>単に int Value;をdouble Value; とすると
>ret = value1->Value - value2->Value;
>でwarningがでます。retはint型なので当然です。強引にビルドして実行すると
>結果はきちんとソートされますが納得いきません。

うまく言っているのはたまたまでしょう。
double から int に型変換をすれば、
切り捨てによる誤差が生じ、正しくソートされる場合と、
正しくソートされない場合が発生する事が考えられます。

>私が理解できていない点は率直に申しますと、
>int compare( const void *area1, const void *area2 )
>{
> const strTestData *value1 = (const strTestData *)area1;
> const strTestData *value2 = (const strTestData *)area2;
> int ret;
>
> /* ----- 比較処理 ----- */
> ret = value1->Value - value2->Value;
>の部分です。

比較関数の戻り値の説明は、前の投稿でしていたと思います。
基本的には、二つの要素を比較し、
その結果、二つの要素が等しい場合には0を、
第一引数の要素が、第二引数の要素より小さい場合には負数、
第一引数の要素が、第二引数の要素より大きい場合には正数を、
それぞれ返せば良い訳です。

浮動小数点数の場合のパターンも、前の投稿で
int compare( const void *area1, const void *area2 )
{
    const double *value1 = (const double *)area1;
    const double *value2 = (const double *)area2;
    int           ret = 0;

    /* ----- 比較処理 ----- */
    if( *value1<*value2 )
    {
        ret = -1;
    }
    if( *value1>*value2 )
    {
        ret = 1;
    }
    return ret;
}

と示しているはずです。
これを応用すれば良いかと思います。


# int 型の場合、比較結果を減算で算出できるのは何故か?
# この辺りを、数学的に考えてみると良いでしょう。


No.1895

Re:折角書いていただいた例を理解したく存じます。調べてはいますが今ひとつ理解できておりません。
投稿者---かずま(2004/06/02 21:33:59)


> # int 型の場合、比較結果を減算で算出できるのは何故か?
> # この辺りを、数学的に考えてみると良いでしょう。

i = 2000000000, j = -2000000000, k = i - j の場合、
i > j ですが、k が正になるとは限りません。



No.1896

Re:折角書いていただいた例を理解したく存じます。調べてはいますが今ひとつ理解できておりません。
投稿者---RAPT(2004/06/02 22:16:50)


C言語では式が真のとき 1、偽のとき 0 となる仕様であることと
3項演算子を使えば、こんなことも。

int compare(const void *a, const void *b)
{
  const int *x = (const int *)a;
  const int *y = (const int *)b;
  return (*x < *y)?(-1):(*x > *y);
}



No.1916

皆様アドバイスありがとうございます。
投稿者---ピヨピヨ(2004/06/04 09:13:50)


おはようございます。

皆様アドバイスありがとうございます。

nop殿
ご指導ありがとうございます。比較関数の戻り値について誤解しておりました。
戻り値に0か負数か正数を返せばいいというところを理解しておりませんでした。
単にretに計算結果を入れたらいいと思っていました。
その結果double型の計算結果がint型retに入ってしまうという質問になってしまいました。申し訳ございません。

正直本を読んでもまだわかっていないところがあります。
>const strTestData *value1 = (const strTestData *)area1;
()のあるなしで意味が変わってくると思います。
左辺は書き換えられない構造体strTestDataを指すポインタがvalue1…
構造体strTestDataの書き換えられないポインタがvalue1が正しいか…
根気よく勉強して身につくようにします(汗)
># この辺りを、数学的に考えてみると良いでしょう。
そうですね。実際数値を入れてケースバイケースで当てはめて考えると
なぜうまくいくのかが見えてきます。適切な助言をありがとうございます。

かずま殿
>i = 2000000000, j = -2000000000, k = i - j の場合、
>i > j ですが、k が正になるとは限りません。
これはint型が扱える値の範囲を超えてしまうからということで理解して
よろしいでしょうか。ご指摘ありがとうございます。

RAPT殿
>C言語では式が真のとき 1、偽のとき 0 となる仕様であることと
>3項演算子を使えば、こんなことも。
アドバイスありがとうございます。私が持っている本にも説明が載ってありました。ご指摘いただいて初めて使い道がわかりました。

入門書がわかる程度にはなってきましたがいろんなプログラム例をみるとわからないことだらけです。(入門書といってもカーニハン&リッチーではありません。一番初めに買わされた本ですが大半が分からないです。)
一つ一つしったかぶらずに確実におさえて身に付けたいと思います。


No.1931

Re:皆様アドバイスありがとうございます。
投稿者---RAPT(2004/06/05 01:31:36)


gt;>const strTestData *value1 = (const strTestData *)area1;
>()のあるなしで意味が変わってくると思います。
(型名)変数 は、キャストといいます。
()をはずすとコンパイルエラーになります。



No.1960

まだまだ知らないことだらけです。もしよろしければ私の理解不足にご指導ください。
投稿者---ピヨピヨ(2004/06/07 11:39:05)


お世話になります。

RAPT殿
>(型名)変数 は、キャストといいます。
>()をはずすとコンパイルエラーになります。
ありがとうございます。
以前nop殿にご指導していただいた際に「キャスト」と
ご説明していただいておりました。私の不注意です。


さて、キャストの使い方について調べています。
例えば
int a ;
double b = 1.23;
a = (int)b;
だとdouble型bをint型にキャストしてaに入れるということは理解しています。

今回私が理解できていない部分に入ります。
以前nop殿に教えていただいたプログラムを抜粋しますと
>int compare( const void *area1, const void *area2 )
>{
> const strTestData *value1 = (const strTestData *)area1;
> const strTestData *value2 = (const strTestData *)area2;

になり、また
>比較関数は、qsort()内部で要素の比較がある時に呼ばれます。
>その際、比較する二つの要素の領域の先頭ポインタ値を引数として渡します。
>比較関数内では、このポインタを適切な型にキャストで当てはめ、
>二つの要素の比較結果を返します。
と教えていただきました。

nop殿の言葉をお借りして、当てはめて考えますと
 敞羈咾垢詁鵑弔陵彖任領琉茲寮萋ポインタ値を引数として渡します。】
引数なのでint compare()の()内を指すことから比較する二つの要素は
const void *area1,const void *area2
となる。先頭ポインタ値を扱うためarea1,area2という値に
const void *
を付ける。(機
「ポインタ値」(*が付いていること)から引数は
要素area1,area2のアドレス値を指している。

◆敞羈售愎内では、このポインタを適切な型にキャストで当てはめ、】
(const strTestData *)area1;
(const strTestData *)area2;
ここを指していると思います。ここの解釈がまだできておりません。
( )はキャストですね。
まずconst void *area1を引数とし、アドレス値で関数に取り込んだ後
area1の値(アドレスの中身)を構造体strTestDataのポインタで捕らえている。
つまり構造体strTestDataのポインタ型をarea1の型にしているということになりますでしょうか?
キャストしたarea1のポインタを構造体strTestDataのvalue1のポインタに
代入しvalue1とvalue2を比較する?
とすると、【二つの要素の比較結果を返します。】の「要素」と
結びついていない…です。
そもそもキャストに*がついていることで戸惑っています。
図を書くことを試みていますが情けないことに理解不足で書けません。

話が逸れて申し訳ありませんが、
(機砲覆voidを付けるのかもよくわかっておりません。
voidは空を指していると理解しております。
変数にvoidを付ける概念が今まで私になかったものですから。
「先頭ポインタ値」をキーワードに調べてみます。

理解の進捗具合をまた投稿させていただきたく思います。
私が間違った方向で理解しておりましたら
大変恐縮ですがご指摘していただいてもよろしいでしょうか。
よろしくお願い致します。


No.1973

Re:まだまだ知らないことだらけです。もしよろしければ私の理解不足にご指導ください。
投稿者---RAPT(2004/06/07 20:23:43)


なんか、滅茶苦茶に勘違いしてますね。

■比較関数の引数、(const void *) 型について
ここでの (const void *) あらゆる型へのポインタを引数として受け取る
事ができるということを意味しています。

受け取るのは (const int *) でも構いませんし、(const char *) でも
構いませんし、(const struct hogehoge *) でも構いません。

void はすべての型を吸収できます。

で、受け取った方ですが、そのままでは型情報がないため、任意の型に
キャストしてやることで利用可能になります。

int fn(const void *x, const void *y);
とすることで、下記のようなどんな型でも対応可能なのです。

int compare_int(const void *x, const void *y)
{
  const int *a = (const int *)x;
  const int *b = (const int *)y;
  return (*a < *b)?(-1):(*a > *b);
}
int compare_char(const void *x, const void *y)
{
  const char *a = (const char *)x;
  const char *b = (const char *)y;
  return (*a < *b)?(-1):(*a > *b);
}

※例えば、動的にメモリを確保する関数に malloc() がありますが、
この関数のプロトタイプは void *malloc(size_t n); であり、

char *p;
p = (char *)malloc(10);

とすることで、char q[10]; とするのとほぼ同等のことができます。
これも、malloc()が返したものを任意の型として利用した一例です。

■qsort()と比較関数について
【比較する二つの要素の領域の先頭ポインタ値を引数として渡します。】
「先頭ポインタ」を引き渡しているのは、qsort() に対してであり、
比較関数に対してではありません。

qsort() は、引数として受け取った配列の個々の要素をアドレス渡しで
比較関数に渡します。

そう、比較関数が受け取るポインタは、qsort() で渡した
被比較配列の要素だったのです!

例えば、
int array[] = {1,7,3,5,9,8,4,2,0,6};
size_t num = sizeof array / sizeof array[0];
size_t width = sizeof array[0];
qsort(array, num, width, compare);
とあったとき、
int ret = compare(&array[0], &array[1]);
等と内部で呼ばれます。ここで、array[0], array[1] はそれぞれint型で
あり、アドレス演算子 & を付加した &array[0] は (int *) 型
になります。

これを比較関数は (const void *) 型で受け取っています。
何度も書きますが、(const void *) 型はあらゆる型を受け取れるのです。

■手抜きサンプル(^^;
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b)
{
  return *(const int *)a < *(const int *)b ? -1 : *(const int *)a > *(const int *)b;
}

int main()
{
  int array[] = {1,7,3,5,9,8,4,2,0,6};
  size_t i, num = sizeof array / sizeof array[0];
  size_t width = sizeof array[0];

  puts("before:");
  for(i = 0; i < num; i++){
    printf("%d  ", array[i]);
  }

  qsort(array, num, width, compare);

  puts("\nafter:");
  for(i = 0; i < num; i++){
    printf("%d  ", array[i]);
  }
  return 0;
}



No.1985

Re:まだまだ知らないことだらけです。もしよろしければ私の理解不足にご指導ください。
投稿者---NykR(2004/06/09 21:21:14)


(1)【比較する二つの要素の領域の先頭ポインタ値を引数として渡します。】
引数なのでint compare()の()内を指すことから比較する二つの要素は
const void *area1,const void *area2
となる。先頭ポインタ値を扱うためarea1,area2という値に
const void *
を付ける。(I)
「ポインタ値」(*が付いていること)から引数は
要素area1,area2のアドレス値を指している。

(引用中、機種依存文字は変更しました)
比較関数には“要素へのポインタ(をconst void*型に変換したもの)”がわたされます。ですから、仮引数area1,area2も「要素」ではなく要素へのポインタを保持することになります。
よって、比較関数はarea1,area2を“要素へのポインタ(をconst void*型に変換したもの)”として取り扱わなければなりません。


(2)【比較関数内では、このポインタを適切な型にキャストで当てはめ、】
(const strTestData *)area1;
(const strTestData *)area2;
ここを指していると思います。ここの解釈がまだできておりません。

void型は、サイズを確定することが出来ません。従って、値を取り出すことも格納することも出来ません。ですから、const voidへのポインタであるarea1やarea2をそのまま間接参照(というのはポインタに単項*演算子を適用することです、念のため)しても何も出来ません。

しかし、これらのポインタは実際には配列の要素を指しているわけですから、“要素へのポインタ”に型変換してから間接参照すれば、要素の値を取り出したり、要素に値を格納したり出来るようになります。

でも、比較関数内で、要素に値を「格納」されたりしては迷惑なのでconstを付けてそれを防止しているのです。const修飾された変数は、値を変更できません


というわけ(?)で汎用のソート関数のサンプル。

#include <stdio.h>

#define N_ELEMENTS(arr) (sizeof(arr)/sizeof(arr[0]))
#define BLOCK(statements) if(1){statements}else do;while(0)
#define SWAP_T(T, o1, o2) BLOCK(T _w=(o1);(o1)=(o2);(o2)=_w;)

static void st_swap(void * p1, void * p2, size_t size)
{
    int i;
    for (i = 0; i < size; i++) {
        SWAP_T(char, ((char*)p1)[i], ((char*)p2)[i]);
    }
}

static void * st_minimum_element( void * begin, void * end, size_t size,
                                  int(*compar)(const void*,const void*) )
{
    char        *minimum_p = begin, *cursor = begin;

    for ( ; cursor != end; cursor += size) {
        if (compar(cursor, minimum_p) < 0) {
            minimum_p = cursor;
        }
    }
    return minimum_p;
}

void selection_sort( void * base, size_t nmemb, size_t size,
                     int(*compar)(const void*,const void*) )
{
    char        *cursor;
    char        *end = &((char*)base)[nmemb*size];
    for (cursor = base; cursor != end; cursor += size) {
        st_swap(cursor, st_minimum_element(cursor, end, size, compar), size);
    }
}

// ここから使用例

static int st_compare_double(const void * key, const void * element)
{
    const double        *k = key, *e = element;
    return (*k > *e) - (*k < *e);
}

void print_array_double (double * array, size_t nmemb)
{
    int i;
    for (i = 0; i < nmemb; i++) {
        printf ("%s%g", i ? ", " : " [", array[i]);
    }
    puts ("]");
}

int main (void)
{
    double      name[] = { 1.0, 5.2, 3.45, 0.002, 12.58, 4.23, 89.65, 0.25,
                           20.11,
    };

    printf("before ");
    print_array_double(name, N_ELEMENTS(name));
    selection_sort(name, N_ELEMENTS(name), sizeof(double), st_compare_double);
    printf("after ");
    print_array_double(name, N_ELEMENTS(name));

    return 0;
}