第６３章 簡単にソートする

実はquick sortをやってくれる関数が用意されています。

void qsort(void *base, size_t num, size_t width, int (__cdecl *compare)(const void *elem1, const void *elem2));

baseには、ソートする配列の先頭を指定します。任意のデータ型Xへのポインタはvoid *型に変換する ことができ、この逆も可能です。変換に際して情報の一部または全部が失われることはありません。 要するにbaseには任意の型へのポインタを指定できます。

numには配列のよう素数を指定します。このデータ型はsize_tなのでsizeof演算子を使って 指定するか、直接数値を指定してsize_t型に型キャストします。

widthには配列の要素のサイズをバイト単位で指定します。これも型はsize_tです。

最後の引数は比較関数へのポインタを指定します。

さて、この関数についている__cdeclというのはマイクロソフト特有の呼び出し規約で ここでは、気にしなくても大丈夫です。

では、具体例を見てみましょう。

// qsort0.c

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

int comp(const void *, const void *);

int main()
{
    int i;
    int test[6] = {10, 8, 2, 6, 4, 0};

    qsort(test, (size_t)6, sizeof(int), comp);

    printf("\n");

    for (i = 0; i < 6; i++)
        printf("%d\n", test[i]);

    return 0;
}

int comp(const void *a, const void *b)
{
    static int i = 1;

    printf("%02d--%d,%d\n", i, *(int *)a, *(int *)b);
    i++;
    return (*(int *)a - *(int *)b);
}

qsort関数を呼びます。配列の先頭はtestになります。要素の数は６、要素の大きさは sizeof(int)バイトとなります。比較関数はここではcompとしました。

qsort関数を実行すると配列testが書き換えられて、要素が昇順に並びます。 これを確かめるためのプログラムを書いておきます。

さて、ここまでは比較的簡単でした。 では、comp関数の中身はどうでしょうか。

ここでは、qsort関数が何と何を比較しているのかを知るために printf関数を呼んでいますが、実際にはreturnの所のみが必要です。

*aが*bより大きい場合は正を小さい場合は負を、同じ場合は０を返すようにします。 そうすると昇順に並びます。正、負を逆にすると降順に並びます。

return(*a - *b);

これを見るとソートが終わるまで１５回比較をしていることがわかります。 どの要素とどの要素を比較しているのかがわかりますね。 また、ソート結果は期待通りになっていますね。

次に、もう一つ例題を見てみましょう。

// qsort.c

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

int com(const void *, const void *);
int com2(const void *, const void *);

int main()
{
    int i;
    int test[] = {2, 0, 1, 9};
    char text[][8] = {"wxy", "mmm", "aaa", "cab", "opqrs"};

        qsort(test, sizeof(test)/sizeof(int), sizeof(int), com);
    for (i = 0; i < 4; i++) {
        printf("%d\n", test[i]);
    }
    qsort((void *)text, sizeof(text) / 8, (size_t)8, com2);
    for (i = 0; i < 5; i++)
        printf("%s\n", text[i]);
    return 0;
}

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

int com2(const void *a, const void *b)
{
    static int i = 1;

    printf("%d -- %s, %s\n", i, (char *)a, (char *)b);
    i++;
    return (strcmp((char *)a, (char *)b));
}

最初に呼んだqsort関数の２番目の引数を見てください。 sizeof(test)がこの配列全体のバイト数です。これをint型のバイト数でわると 要素の個数がわかります。(だからこの関数の２番目の引数がsize_t型になっている)

２番目に呼んだqsort関数も引数を検討してみてください。 また、それぞれのqsort関数の比較関数が違う点にも注意してください。

では、実行結果を見てみましょう。

さて、qsort関数は元々の配列を書き換えてしまうので、これを残しておく 必要がある場合は、コピーを作って並び替えをしてもらう必要があります。

いろいろな配列について並び替えをするプログラムを作ってみてください。 降順の並び替えもしてみてください。