qsort関数
qsort関数は第一引数に指定された配列を、第四引数に指定された比較関数の規則に沿って並び替えます。第二引数には配列のサイズ、第三引数には配列要素のデータサイズを指定します。
定義詳細
#include <stdlib.h>
void qsort(
void *base, size_t num, size_t size,
int (*compare)(const void *a, const void *b)
);
第一引数 | base | ソート対象の配列 |
第二引数 | num | 配列要素の個数 |
第三引数 | size | 配列要素のサイズ |
第四引数 | compare | 比較関数(コールバック関数) |
// 比較関数
int (*compare)(const void *a, const void *b)
比較関数の状態 | 戻り値 |
---|---|
第一引数の方が小さい | 負の値 |
両方の引数が等しい | 0 |
第一引数の方が大きい | 正の値 |
比較関数のルール
第四引数には、独自定義した比較関数をコールバック関数として渡します。並び替え実行時、比較関数には整列対象の要素が順次、実引数として渡されてきます。
qsort関数は、比較関数の戻り値を元に、各要素を昇順に整列します。一つ目の仮引数の値のほうが小さいに場合には、0より小さい数値を返し、二つ目の仮引数のほうが小さい場合には、0より大きい数値を返す必要があります。両引数の値が同等の場合は0を返します。
正と負の戻り値に対する判断基準を逆転させることで、降順による整列を実現することも可能です。比較関数の第一引数が第二引数より小さい場合には正の値を返し、逆の場合には負の値を返すようにします。
qsort関数の使い方
昇順
配列を昇順で整列する方法です。ascが実際の比較関数となります。
int asc(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int main() {
int a[] = {2, 3, 1};
qsort(a, sizeof(a) / sizeof(int), sizeof(int), asc);
printf("%d%d%d", a[0], a[1], a[2]); // "123"
}
asc関数の実装は# 比較関数のルールに沿った形となっています。逆に、不等号による比較(return *(int *)a < *(int *)b;
)は意図しない結果を招くため利用しないよう注意してください。必ず「正の数」と「負の数」と「0」の3パターンの的確な戻り値を返す必要があります。
long型の場合
long型の演算結果をそのまま比較関数の戻り値に使うと、int型のオーバーフローが発生し、正確な整列が行えなくなるため、注意してください。
int asc(const void *a, const void *b) {
// 警告: Implicit conversion loses integer precision: 'long' to 'int'
return *(long *)a - *(long *)b;
}
次のように、より厳格な戻り値を返すようにする必要があります。
int asc(const void *a, const void *b) {
long *A = (long *)a;
long *B = (long *)b;
if (*A > *B) return 1;
if (*A < *B) return -1;
return 0;
}
降順
int desc(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int main() {
int a[] = {2, 3, 1};
qsort(a, sizeof(a) / sizeof(*a), sizeof(*a), desc);
printf("%d%d%d", a[0], a[1], a[2]); // "321"
}
文字列要素の並び替え
文字列オブジェクトに対する並び替えも可能です。strcmp関数の戻り値(負の値, 0, 正の値
のいずれかを返す)を比較関数側の戻り値として活用するとよいでしょう。
int compare_string(const void *a, const void *b) {
return strcmp(*(const char **)a, *(const char **)b);
}
int main() {
const char *names[] = {"Bob", "Ann", "Chris"};
qsort(names, 3, sizeof *names, compare_string);
printf("%s,%s,%s", names[0], names[1], names[2]);
// 表示結果: "Chris,Bob,Ann"
}
比較関数の注意点と罠
比較関数の仮引数には各要素へのポインタが渡ってきます。文字列要素const char *
はダブルポインタ(const char **
)として渡ってくることになる点に注意してください。そのため、*(const char **)a
による間接参照が必要となります。
なおstrcmp((const char *)a, (const char *)b)
と記述しても警告や実行時エラーが発生しないことがほとんどです。これらはバグの原因にも繋がるため注意してください。
構造体の並び替え
配列の要素が構造体の場合でもソートが可能です。
struct Person {
int person_id;
const char *person_name;
};
int compare_person_id(const void *a, const void *b) {
struct Person *A = (struct Person *)a;
struct Person *B = (struct Person *)b;
return A->person_id - B->person_id;
}
int main() {
struct Person persons[] = {
{2, "Bob"}, {3, "Ann"}, {1, "Chris"},
};
qsort(persons, 3, sizeof(struct Person), compare_person_id);
printf("%s,%s,%s", persons[0].person_name, persons[1].person_name, persons[2].person_name);
// 表示結果: "Chris,Bob,Ann"
}