このページでは、C言語の標準関数である qsort
関数の使い方について解説します。
qsort
関数とは
まず、この qsort
関数がどのような関数であるのかについて解説します。
配列をベースに解説しますが、malloc
関数などで確保したメモリ上のデータでも同様のことを行うことが可能です
qsort
関数は配列をソートする関数
qsort
は、引数で指定した配列の各データをソートする関数です(並び替えする関数)。
ソートを行う際に用いられるアルゴリズムは「クイックソート」です。qsort
の q
を quick
と考えると関数名が覚えやすいと思います。
クイックソートは名前の通り、ソート速度が高速である点が特徴です。クイックソートがどのようなアルゴリズムであるかは下記ページで解説していますので、詳しく知りたい方は是非下記ページを読んでみてください。
クイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)上のページを読んで見ていただければ分かると思いますが、クイックソートを行うためにはそれなりに実装は必要ですし、実装するためにはクイックソートがどんなものであるかを理解しておかなければなりません。
ですが、qsort
関数を利用すれば、わざわざクイックソートを自身でプログラミングしなくても、関数を呼び出すだけでクイックソートによるソートを実現することができます。
さらに、この qsort
関数では、どんな型の配列であってもソート可能であるという特徴を持ちます。
整数の配列をソートすることもできますし、文字列の配列をソートすることもできます。さらには、あなたが作成した構造体の配列でもソートすることができてしまいます。
さらに、qsort
関数では、配列の各データを昇順および降順のどちらでもソート可能です。
スポンサーリンク
比較関数を自作する必要あり
ここまでの解説だけ読むと、この qsort
関数はかなり便利な関数に思えますね!
実際便利なのですが、便利である代わりに、ソート時に実行される “比較を行う関数(以降では比較関数と呼びます)” を作成し、その関数のアドレスを qsort
関数に渡してやる必要があります。ちょっとここがややこしいです。
要はソートとは、各データの大小関係を比較しながら、データ全体(配列全体)が昇順 or 降順に並ぶようにデータの並び替えを行う処理です。
ですが、その大小関係の比較自体は qsort
関数の中では行われません。なので、qsort
関数の利用者がその比較を行う関数を作成し、その関数のアドレスを qsort
に渡してやる必要があります。
そうすることで、比較を行う必要がある際に qsort
関数からその比較関数が実行され、その関数の結果に基づいてソートが行われるようになります。
比較関数を作成する必要があるのでちょっと手間はかかりますが、自分で好きなように比較関数を作成することができるため、上記のようにさまざまなソートを行うことが可能になっています。
基本的な qsort
関数の利用例
例えば下記では、int
型の配列 array
の各データを昇順にソートする場合の qsort
関数の利用例になります(比較関数は compare
)。
#include <stdio.h>
#include <stdlib.h>
/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
int ret;
const int *p_int1 = p_data1;
const int *p_int2 = p_data2;
printf("%d と %d の比較\n", *p_int1, *p_int2);
if (*p_int1 < *p_int2) {
ret = -1;
} else if (*p_int1 > *p_int2) {
ret = 1;
} else {
ret = 0;
}
return ret;
}
int main(void) {
int i;
int array[10] = {
8, 1, 9, 6, 7, 3, 5, 0, 2, 4
};
/* qsort関数の実行 */
qsort(&array[0], 10, sizeof(array[0]), compare);
for (i = 0; i < 10; i++) {
printf("%d, ", array[i]);
}
printf("\n");
return 0;
}
実行すると下記のように表示され、最後の1行から配列 array
のデータが昇順にソートされていることが確認できると思います。
8 と 3 の比較 3 と 4 の比較 8 と 4 の比較 〜略〜 9 と 8 の比較 7 と 8 の比較 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
また、他の行の出力から比較関数 compare
が何回も実行されていることと、配列 array
のデータ(のアドレス)が比較関数 compare
の引数として渡されていることが確認できると思います(”8 と 3 の比較” といった比較時の情報を表示しているのは compare
関数)。
compare
関数は main
関数からは実行しておらず、前述の通り qsort
関数から実行されています。こんな感じで qsort
関数を実行すると、比較関数を実行してデータの比較を行い、その比較結果に応じてソートが行われます。
大体 qsort
関数の動作や比較関数との関係性は理解してもらえたのではないかと思いますので、ここからは個別に下記について解説していきたいと思います。
qsort
関数の使い方- 比較関数の作り方
qsort
関数の使い方
それでは qsort
関数の使い方(実行の仕方)について解説していきます。
スポンサーリンク
qsort
関数の定義
まず qsort
の関数定義を確認してみましょう!qsort
の関数定義は下記のようになります。
#include <stdlib.h>
void qsort(void *elems, size_t num_elem, size_t size_elem, int (* compar)(const void *, const void *));
まず qsort
は stdlib.h
で宣言されていますので、qsort
を使用する際には stdlib.h
を include
する必要があります。
また、戻り値の型は void
ですので、要は戻り値は “なし” です。
qsort
関数の引数
さらに、qsort
関数の各引数には下記を指定します。
- 第1引数
elems
:ソートを開始するデータのアドレス - 第2引数
num_elem
:ソート対象のデータの数 - 第3引数
size_elem
:ソート対象の各データのサイズ(バイト) - 第4引数
compare
:比較関数のアドレス
上記の引数に対し、qsort
関数では、アドレス elems
から num_elem
個分のデータ(各データのサイズは size_elem
)をソート対象として、ソートが実行されます。ソートに必要な比較は compare
の指す関数により行われます。
第1引数の型は void *
で難しそうに感じるかもしれませんが、要はどんな型のアドレスを指定してもオーケーということです。一番よく指定するのは配列の先頭アドレスで、int
型の配列や構造体の配列等の先頭アドレスを指定することが可能です。
第4引数に関しては、関数のアドレスを指定するところが難しそうですが、C言語では単に関数名を記述することで、その関数のアドレスを取得することが可能です。
ですので、きちんと比較関数さえ作成していれば、後はその関数名を第4引数に指定すれば良いだけです(比較関数の作り方については、後述の比較関数の作り方で解説します。
qsort
関数の基本的な使い方
例えば、下記のような配列の全体をソートしたい場合について考えてみましょう。
int array[100];
この場合、配列名は array
、配列のデータ数は 100
、配列の型は int
なので、qsort
関数を下記のように実行することになります(比較関数の名前は compare
としています)。
qsort(array, 100, sizeof(int), compare);
上記のように qsort
関数を実行すると、array[0]
〜 array[99]
のデータがソートされた状態になります(比較関数 compare
を比較関数の作り方で説明した内容に基づいて作成していれば)。
また、下記のように qsort
関数を実行したとしても同じ結果を得ることができます。
qsort(&array[0], 100, sizeof(array[0]), compare);
スポンサーリンク
qsort
関数による配列の特定の範囲のみのソート
また、少し特殊な使い方になるかもしれませんが、配列全体ではなく配列の途中のデータのみをソートしたいような場合は、その範囲が特定できる形で qsort
関数を実行する必要があります。
例えば前述の配列 array
の array[30]
〜 array[69]
の 40
個のデータのみをソートしたいような場合は、下記のように qsort
関数を実行する必要があります。
qsort(&array[30], 40, sizeof(int), compare);
要は、”ソートを開始するデータのアドレス” が &array[30]
なので、これを第1引数に指定し、”ソートを行うデータの数” が 40
なので、これを第2引数に指定しています。
こんな感じで、特に第1引数と第2引数の指定を工夫することで、ソートを行う対象の範囲を変更することが可能です。
qsort
関数による構造体の配列のソート
また、前述の通り、qsort
関数ではどんな型のデータであってもソートすることが可能です。例えば下記のように構造体の配列に対して qsort
関数を実行することも可能です(比較関数 compare
の定義は省略しています)。
#include <stdlib.h>
#define NUM_PEOPLE 10
typedef struct _PERSON {
int age;
int weight;
int height;
char name[256];
} PERSON;
int main(void) {
PERSON people[NUM_PEOPLE];
/* 配列の初期化 */
qsort(people, NUM_PEOPLE, sizeof(PERSON), compare);
return 0;
}
基本は前述の int
の配列をソートする時と同じですが、第3引数で指定する “各データのサイズ” が異なるのでこの点だけは注意しましょう。
qsort
関数の使い方の解説は以上になります。
で、ここまでの解説を聞いて下記のような疑問を抱いた方もおられるのではないでしょうか?
- 昇順ソートと降順ソートはどうやって指定するの?
- 構造体の場合、どのメンバに対してソートされるの?
これらは引数で指定するのではなく、第4引数で指定するアドレスの “比較関数” によって決まります。つまり、比較関数の作り方によって昇順ソート or 降順ソートのどちらでソートを行うかや、構造体のどのメンバでソートするのかが決まります。
ということで、次は比較関数の作り方について解説していきたいと思います。
比較関数の作り方
それでは、比較関数の作り方について解説していきたいと思います。
まずは比較関数の役割を簡単におさらいしておきます。
前述の通り、比較関数は qsort
関数から実行される関数です。
この qsort
関数から実行される際、比較関数には2つのデータの格納されたアドレスが引数として渡されます。これらのデータはソート対象のデータのうちの2つになります。
比較関数の役割は、その2つのデータの大小関係を比較し、その結果に応じた値を返却することです。
qsort
関数は、その返却された値に応じてソート処理を進めますので、比較関数が正しく大小関係に応じた値を返却しないと、ソート結果も正しくなりません。
では、このような役割を持つ比較関数をどうやって作成していけば良いのかについて解説していきます。
スポンサーリンク
比較関数の引数の型と戻り値の型を指定する
まずは作成する比較関数の “引数の型” と “戻り値の型” について解説していきます。
みなさんも関数を作成する時には引数の型と戻り値の型を決めますよね?
当然ですが、今回作成する比較関数においても引数の型と戻り値の型を決める必要があります。ではどのように決めれば良いでしょうか?
この答えは、qsort
の関数定義を見れば分かります。再掲ですが、下記が qsort
の関数定義になります。
#include <stdlib.h>
void qsort(void *elems, size_t num_elem, size_t size_elem, int (* compar)(const void *, const void *));
注目していただきたいのが第4引数です。前述の通り、qsort
関数実行時には、この第4引数に比較関数のアドレスを指定します。
この第4引数の型、すごく難しそうに見えますが、要は下記のような比較関数のアドレスを引数に指定して欲しいことを示しています。
- 戻り値の型:
int
- 第1引数の型:
const void *
- 第2引数の型:
const void *
つまり、作成する比較関数(qsort
関数の第4引数に渡すアドレスの関数)の戻り値の型と引数の型は上記のようになります。
ですので、関数の大枠だけを書けば下記のようになりますね!
int 関数名(const void *引数名1, const void *引数名2) {
int ret;
/* 関数の中身 */
return ret;
}
あとは、関数名と引数の名前を付け、さらにこの関数の中身を記述してやれば良いだけです。関数名や引数名は、予約語やスコープ内の他の変数・関数の名前と被っていなければなんでも良いです。
ポインタ引数をソート対象のデータの型のポインタに変換する
ただ、2つの引数が const void *
型である点に注意が必要です。
ひとまず const
は置いておいて解説すると、引数の型である void *
型は、どんな型のデータでも指すことが可能なポインタの型になります。ですので、引数が void *
型である比較関数は、どんな型のデータであってもアドレスとして受け取ることが可能です。
一方で、void *
型のポインタ変数に対しては、間接演算子(*
)や添字演算子([]
)を利用することができません。つまり、void *
型のポインタ変数では、これらの演算子を利用してポインタの指す先のデータを取得することができないのです(void *
型のポインタに対して間接演算子や添字演算子を利用するとコンパイルエラーになります)。
なので、間接演算子(*
)や添字演算子([]
)を利用してポインタの指す先のデータを取得するためには、一旦引数の型を他の型のポインタに変換する必要があります。
変換先の型は、”ソート対象のデータの型のポインタ” になります。
これは、比較関数のポインタ引数には、ソート対象のデータのいずれかのアドレスが格納されているからです(比較を行うデータのアドレス)。
もっと具体的にいえば、1次元配列をソートする場合は、その配列の型のポインタに変換を行えば良いです。例えば int
型の配列をソートする場合、ポインタ引数を int *
型のデータに変換します。
また、ここまで const
は無視して解説してきましたが、実際には引数の型は const void *
で const
指定されていますので、変換先の型にも const
指定する方が良いです。
これは、間違ってポインタ引数の指す先のデータを変更してしまわないようにするためです。
さらに、ここまで解説した型の変換は、キャスト演算子 (型名)
を利用しても良いですが、単に変換先の型の変数にポインタ引数の値を代入するだけで行うことも可能です。
下記は、int
型の配列をソートする場合に、ポインタ引数 p_data1
と p_data2
それぞれの値を、const int *
型の変数 p_int1
と p_int2
に代入する例になります。
int compare(const void *p_data1, const void *p_data2) {
int ret;
const int *p_int1 = p_data1;
const int *p_int2 = p_data2;
/* 関数の中身 */
return ret;
}
p_data1
や p_data2
では間接演算子を利用することはできませんが、p_int1
や p_int2
では間接演算子を利用することができるので、上記のような代入により、*p_int1
や *p_int2
よりポインタ引数の指すデータを取得することが可能になります。
この辺りの void *
型や const
指定については下記ページで詳細を解説していますので、詳しく知りたいかたはこちらを参照していただければと思います。
ポインタ引数が指すデータの大小関係に応じて値を返却する
上記により、ポインタ引数が指すデータを間接演算子(or 添字演算子)を利用して取得できるようになったので、あとは2つのポインタ引数が指すデータの大小関係に応じて値を返却してやれば良いです。
この返却する大小関係に応じた値は、昇順ソートを行う場合と降順ソートを行う場合とで異なります。
具体的な違いは下記のようになります(第1引数のポインタが指すデータを “データ1”、第2引数のポインタが指すデータを “データ2” として説明しています)。
- 昇順ソートする場合
データ1 < データ2
:0
より小さい値データ1 > データ2
:0
より大きい値データ1 == データ2
:0
- 降順ソートする場合
データ1 < データ2
:0
より大きい値データ1 > データ2
:0
より小さい値
:データ1 == データ2
0
要は、昇順ソートと降順ソートとでは、データ1 < データ2
の場合と データ1 > データ2
の場合とで返却する値が逆になります。
昇順ソートの場合
例えば、int
型の配列のデータを “昇順ソート” する際には、下記のようにポインタ引数の指す2つのデータを比較し、その比較結果に応じて値を返却します。
int compare(const void *p_data1, const void *p_data2) {
int ret;
const int *p_int1 = p_data1;
const int *p_int2 = p_data2;
if (*p_int1 < *p_int2) {
ret = -1;
} else if (*p_int1 > *p_int2) {
ret = 1;
} else {
ret = 0;
}
return ret;
}
降順ソートの場合
int
型の配列のデータを “降順ソート” する際には、下記のようにポインタ引数の指す2つのデータを比較し、その比較結果に応じて値を返却します。
int compare(const void *p_data1, const void *p_data2) {
int ret;
const int *p_int1 = p_data1;
const int *p_int2 = p_data2;
if (*p_int1 < *p_int2) {
ret = 1;
} else if (*p_int1 > *p_int2) {
ret = -1;
} else {
ret = 0;
}
return ret;
}
昇順ソートを行う場合のものと比較して、返却値の符号が逆になっているところがポイントです。
int
型の数値そのものを扱う型であれば、上記のように単純に比較演算子(<
や >
)を利用して比較を行えば良いので簡単ですが、文字列をソートするような場合は、strcmp
関数などを利用して比較を行うことになります。
また、構造体をソートするような場合は、構造体のあるメンバの値に対して比較を行い、大小関係に応じた値を返却することになります。
これらの具体的な処理内容に関しては、次の qsort 関数を利用したソート例の中で紹介していきたいと思います。
スポンサーリンク
qsort
関数を利用したソート例
最後に qsort
関数でソートを行うソースコードをいくつか紹介しておきたいと思います。
このソート例をみていただくことで qsort
関数の使い方の参考にもなると思いますし、また比較関数が自作できるおかげで様々なソートを行うことができるということも実感できると思います。
整数の配列を qsort
関数でソートする
ここまでにも整数の配列を qsort
関数でソートする例は示してきましたが、全てソート対象のデータの型が int
だったので、ここでは short
型の配列を qsort
関数でソートする例を示したいと思います。
#include <stdio.h>
#include <stdlib.h>
/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
int ret;
const short *p_short1 = p_data1;
const short *p_short2 = p_data2;
if (*p_short1 < *p_short2) {
ret = -1;
} else if (*p_short1 > *p_short2) {
ret = 1;
} else {
ret = 0;
}
return ret;
}
int main(void) {
int i;
short array[10] = {
8, 1, 9, 6, 7, 3, 5, 0, 2, 4
};
/* qsort関数の実行 */
qsort(&array[0], 10, sizeof(short), compare);
for (i = 0; i < 10; i++) {
printf("%d, ", array[i]);
}
printf("\n");
return 0;
}
簡単にポイントを説明しておきたいと思います。
ポイント1:ポインタ引数は const short *
に変換する
上記の比較関数は、基本的な qsort 関数の利用例で示した int
型の配列をソートする時のものとほぼ変わりません。実質的に異なるのはポインタ引数の変換先の型が const short *
に変わったことのみです。
なぜ変換先の型が変わったかというと、これはソート対象のデータの型が short
に変化したからです。これにより、比較関数のポインタ引数が指すデータも short
型になりますので、変換先の型も short *
に変更しています(さらには比較関数内部で誤ってポインタ引数の指すデータを変更しないように const
指定しています)。
ポイント2:各データのサイズは “short
型のサイズ”
また qsort
関数の第3引数には、ソート対象の各データのサイズを指定する必要があります。つまり、今回はソート対象の各データが short
型なので、short
型のサイズを指定する必要があります(short
型のサイズは一般的には 2
バイトになります)。
型のサイズは sizeof
演算子を用いることで取得できるので、上記の例では sizeof(short)
により、qsort
関数の第3引数を指定しています。
この例では short
型のサイズを指定していますが、ソート対象の各データのサイズを指定さえすれば良いので、ソート対象の配列 array
の中のいずれかの要素、例えば第 0
要素のサイズを sizeof
演算子で取得し、それを qsort
関数の第3引数に指定するのでも良いです(つまり sizeof(array[0])
を指定する)。
文字列の配列を qsort
関数でソートする
文字列の配列を qsort
関数でソートする例は下記のようになります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcmp */
int compare(const void *p_data1, const void *p_data2) {
const char *p_str1 = p_data1;
const char *p_str2 = p_data2;
return strcmp(p_str1, p_str2);
}
int main(void) {
int i;
char array[7][256] = {
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday"
};
qsort(&array[0][0], 7, sizeof(array[0]), compare);
for (i = 0; i < 7; i++) {
printf("%s\n", array[i]);
}
return 0;
}
今回紹介する qsort
の利用例の中で難易度は一番高いと思います。
ポイントは3つです。
ポイント1:比較には strcmp
を利用する
ポイントの1つ目は strcmp
を使用しているところです。
文字列の場合は、単なる比較演算子で比較を行うのが大変なので、比較関数 compare
では strcmp
を使用して比較を行なっています。
strcmp
はアルファベット順的に考えて、第1引数の文字列が第2引数の文字列よりも前側に存在する場合に 0
よりも小さい値を、後ろ側に存在する場合に 0
よりも大きい値を、2つの引数の文字列が同じ場合は 0
を返却しますので、compare
関数ではこの strcmp
の戻り値をそのまま返却するようにしています。
ちなみに、strcmp
の戻り値に -1
を掛けて返却することで、降順ソートを実現することも可能です。
return strcmp(p_str1, p_str2) * (-1);
ポイント2:ポインタ引数は const char *
に変換する
ポイントの2つ目は、compare
関数におけるポインタ引数の変換先の型です。
compare
関数が実行された際、p_data1
と p_data2
には配列 array
に格納された各文字列の “先頭の文字” の位置のアドレス(つまり char
型のデータのアドレス)が格納されることになりますので、一旦 const char *
型に変換してから strcmp
関数を実行しています。
ポイント3:各データのサイズは “文字の配列のサイズ”
ポイントの3つ目は、qsort
の第3引数です。
今回は文字列の配列 array
がソート対象であり、この配列 array
の各データは文字列です。さらにC言語においては、文字列は “文字の配列” として扱われるため、結局はこの “文字の配列” のサイズを第3引数に指定する必要があります。
その文字の配列のサイズは sizeof(array[0])
で取得できるので、qsort
の第3引数には sizeof(array[0])
を指定するようにしています。
配列 array
は下記のように宣言しているため、文字の配列のサイズ、すなわち sizeof(array[0])
は 256
バイトとなります。
char array[7][256] = {
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday"
};
さらに、その文字の配列が配列 array
には 7
個あるので、第2引数には 7
を指定しています。
もし、第3引数に単に char
型のサイズを指定してしまうと上手くソートが出来ません。あくまでも qsort
関数の第3引数に指定すべきなのは “ソート対象の各データのサイズ” です。単純に型のサイズを指定すれば良いというものではないので注意してください。
スポンサーリンク
構造体の配列を qsort
関数でソートする
構造体の配列を qsort
関数でソートする例は下記のようになります。構造体としては PERSON
というものを定義し、PERSON
型の配列の各データを init
関数でランダムに初期化してからソートを行っています。
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcmp */
#include <math.h> /* pow */
/* データの個数 */
#define NUM_PEOPLE 10
/* 名前の配列 */
char *names[] = {
"ichiro", "jiro", "saburo", "shiro", "goro",
"rokuro", "nanaro", "hachiro", "kuro", "zyuro"
};
typedef struct _PERSON {
int age;
int weight;
int height;
char name[256];
} PERSON;
static int compare_age(const void *p_data1, const void *p_data2) {
int ret;
const PERSON *person1 = p_data1;
const PERSON *person2 = p_data2;
if (person1->age < person2->age) {
ret = -1;
} else if (person1->age > person2->age) {
ret = 1;
} else {
ret = 0;
}
return ret;
}
int compare_name(const void *p_data1, const void *p_data2) {
int ret;
const PERSON *person1 = p_data1;
const PERSON *person2 = p_data2;
if (strcmp(person1->name, person2->name) < 0) {
ret = -1;
} else if (strcmp(person1->name, person2->name) > 0) {
ret = 1;
} else {
ret = 0;
}
return ret;
}
int compare_bmi(const void *p_data1, const void *p_data2) {
int ret;
const PERSON *person1 = p_data1;
const PERSON *person2 = p_data2;
int bmi1 = person1->weight / pow(((double)person1->height / (double)100), 2);
int bmi2 = person2->weight / pow(((double)person2->height / (double)100), 2);
if (bmi1 < bmi2) {
ret = -1;
} else if (bmi1 > bmi2) {
ret = 1;
} else {
ret = 0;
}
return ret;
}
void init(PERSON *people, int num) {
int i;
for (i = 0; i < num; i++) {
/* 乱数を使って適当に初期化 */
people[i].age = rand() % 100;
people[i].weight = rand() % 50 + 50;
people[i].height = rand() % 100 + 100;
strcpy(people[i].name, names[rand() % 10]);
}
}
void print(PERSON *people, int num) {
int i;
for (i = 0; i < num; i++) {
printf("people[%d]:\n", i);
printf(" age = %d\n", people[i].age);
printf(" weight = %d\n", people[i].weight);
printf(" height = %d\n", people[i].height);
printf(" name = %s\n", people[i].name);
}
}
int main(void) {
PERSON people[NUM_PEOPLE];
init(people, NUM_PEOPLE);
print(people, NUM_PEOPLE);
/* age に対して昇順ソート */
printf("[ageに対して昇順ソート]\n");
qsort(people, NUM_PEOPLE, sizeof(people[0]), compare_age);
print(people, NUM_PEOPLE);
/* BMI に対して昇順ソート */
printf("[BMIに対して昇順ソート]\n");
qsort(people, NUM_PEOPLE, sizeof(PERSON), compare_bmi);
print(people, NUM_PEOPLE);
/* name に対して昇順ソート */
printf("[nameに対して昇順ソート]\n");
qsort(people, NUM_PEOPLE, sizeof(PERSON), compare_name);
print(people, NUM_PEOPLE);
return 0;
}
このソースコードでは、下記の3つの比較関数を用意しています。
compare_age
:PERSON
型の配列のデータを、age
メンバに対して昇順ソートするための比較関数compare_name
:PERSON
型の配列のデータを、name
メンバに対して昇順ソートするための比較関数compare_bmi
:PERSON
型の配列のデータを BMI に対して昇順ソートするための比較関数
ポイント1:メンバの値を参照して比較を行う
構造体の場合は、構造体のどれかのメンバに対してソートを行うのが基本だと思います。つまり比較関数では、構造体のメンバの値の大小関係を比較する必要があります。
で、このメンバにアクセスするためには型が const void *
のままではダメなので、比較関数では比較を行う前にソートを行うデータの型である PERSON
のポインタ、つまり PERSON *
型の変数にポインタ引数の値を代入するようにしています。
さらに、compare_age
においては age
メンバ、compare_name
においては name
メンバの大小関係を比較し、その結果に応じて値を返却するようにしています(name
の場合は文字列なので、strcmp
によりアルファベット順的に前にあるか後ろにあるかの比較を行なっています)。
ちなみに、単なる構造体ではなく、構造体のポインタからメンバにアクセスするためにはアロー演算子(->
)を用いるのが一般的です。
アロー演算子については下記ページで解説していますので、どういった演算子であるかを知りたい方はぜひ読んでみてください(私のサイトで一番人気のあるページです)。
C言語のアロー演算子(->)を分かりやすく、そして深く解説ポイント2:メンバにないデータに対するソートも可能
compare_age
や compare_name
は単純に構造体のメンバの値の比較を行なっていますが、別にメンバの値そのものの比較ではなく、メンバの値から求められる他の値を比較するようなこともできます。その例が compare_bmi
になります。
compare_bmi
では、weight
メンバと height
メンバの値から BMI を計算し、その BMI の大小関係に応じて値を返却するようにしています。これにより、構造体のメンバにはない BMI に対して配列のデータのソートを行うことが可能です。
ただ、これは比較関数の作り方によって様々なソートを行うことができることを例として示しているだけで、実はソート速度が遅くなるのであまりオススメはしないです。
これは、比較関数で実行される処理の量が増えるからです。この例であれば、BMI を計算するための演算の分、処理量が増えることになります。
データの並びにもよりますが、一般的に ソート対象のデータの数 < 比較回数
となるので、比較関数の中で処理を行うよりかは、ソートを実行する前にあらかじめ必要な処理を行なった結果を構造体のメンバに保持しておく方がソート速度は速いです。
この例であれば、bmi
メンバを構造体 PERSON
に追加し、BMI の計算結果をその bmi
メンバに代入してから qsort
関数を実行し、比較関数の中では bmi
メンバの大小比較のみを行なった方がソート速度が速くなります。
その他のソート関数
ここまではクイックソートを行う qsort
関数について解説してきましたが、その他にもソートを行う関数がC言語の標準ライブラリには用意されています。
特に下記の2つについては、qsort
関数と同様の使い方でソートを行うことが可能です。
heapsort
:ヒープソートによりソートを行う関数mergesort
:マージソートによりソートを行う関数
比較関数が必要な点や、その比較関数の作り方、引数の指定は qsort
関数と全く同じです。
ただ下記の2点の違いがあるのでその点だけ注意して使用していただければと思います。
- 戻り値の型が
int
型である(qsort
ではvoid
型)- エラー時には
-1
が、正常終了時には0
が返却されます
- エラー時には
mergesort
関数の第3引数がsizeof(void *)
より小さいとエラーになる- なぜこれでエラーになってしまうかの理由はよく分からないです…
- 64 bit CPU の場合は
sizeof(void *)
はおそらく8
になるので、サイズが4
未満の型の配列のソートは行えないことになります
まとめ
このページではC言語の標準関数である qsort
関数の使い方について解説しました!
データのソートを行いたい場面は割と多いと思いますが、ソートを実装するのはそれなりに大変です。ですが、今回紹介した qsort
関数を利用することで、簡単にソートを実現することができます。しかもどんな型のデータでもソートできるのでかなり便利です。
一見 qsort
関数の引数の型は難しく見えますが、qsort 関数の使い方で解説した内容や、qsort 関数を利用したソート例で示した実例より、割とシンプルに使用できる関数であることが確認できると思います。
また、qsort
関数を実行するためには比較関数が必要になりますので、事前に比較関数を作成してから qsort
関数を実行するようにしましょう。
比較関数を作らなければならない代わりに、qsort
関数では様々なソートを行うことができます。ぜひ比較関数を作成する際には、比較関数の作り方で解説した内容や、qsort 関数を利用したソート例で示した実例を参考にしてみてください!
また、C言語で力試しをしてみたい方は是非この qsort
関数を作成してみてください(引数は実際の qsort
関数のままで)。
void *
のポインタの扱いや、コールバック関数の利用など、学べることがかなり多いと思います!