第63章 簡単にソートする


今回は、表題の通り簡単にソートするプログラムについて考えます。 ソートについてはすでに第31章で解説しましたが、これはもっとも原始的で 効率の悪い方法でした。これよりほんの少し効率の良いソート法にquick sortと いうのがあります。具体的なソート法についてはここでは触れません。



実は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); }

まず、int型の配列testを用意して、要素に適当なデータを入れておきます。 この要素を昇順に並び替えてみましょう。

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

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

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

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

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

return(*a - *b);

としてもよさそうに思いますが、これはエラーとなります。 この関数の引数はvoid *型なのでこれでは計算ができません。 そこでaをint型へのポインタであることを示すために(int *)aとします。 これの参照はずしで*(int *)aとなります。

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



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

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

今度は、int型の配列と、文字列の配列を要しました。 これらをソートします。文字列の方は辞書式にソートします。

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

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

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

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



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


[Index][総合Index] [Previous Chapter] [Next Chapter]

Update Apr/04/2001 By Y.Kumei
当ホーム・ページの一部または全部を無断で複写、複製、 転載あるいはコンピュータ等のファイルに保存することを禁じます。