C言語の基礎 - ソート関数

qsort関数とは

qsort関数は、第1引数に指定された配列を、第4引数に指定された比較関数の規則に沿って並び替える。 第2引数には配列のサイズ、第3引数には配列要素のデータサイズを指定する。

定義の詳細

 #include <stdlib.h>
 void qsort(void *base, size_t num, size_t size, int (*compare)(const void *a, const void *b));
 第1引数	base     ソート対象の配列
 第2引数	num      配列要素の個数
 第3引数	size     配列要素のサイズ
 第4引数	compare  比較関数(コールバック関数)
 
 // 比較関数
 int (*compare)(const void *a, const void *b)
 比較関数の状態         戻り値
 第1引数の方が小さい	負の値
 両方の引数が等しい	0
 第1引数の方が大きい	正の値

qsort関数の使い方

昇順

配列を昇順で整列する方法を下記に記述する。 尚、asc関数は比較関数である。

 // int型の場合
 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]);
    // 表示結果 : "1, 2, 3"
 }

 // long型の場合
 // long型の演算結果をそのまま比較関数の戻り値に使うと、int型のオーバーフローが発生し、正確な整列が行えなくなるため、注意すること
 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 main()
 {
    long a[] = {2, 3, 1};
    qsort(a, sizeof(a) / sizeof(long), sizeof(long), asc);
    printf("%d, %d, %d", a[0], a[1], a[2]);
    // 表示結果 : "1, 2, 3"
 }

 // 文字列の場合
 // strcmp関数の戻り値(負の値, 0, 正の値のいずれかを返す)を比較関数側の戻り値として活用するとよい。
 
 int compare_string(const void *a, const void *b)
 {
    return strcmp(*(const char **)b, *(const char **)a);
 }
 
 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]);
    // 表示結果 : "Ann, Bob, Chris"
 }

 // 構造体の場合
 struct tag_PERSON
 {
    int person_id;
    const char *person_name;
 }PERSON;
 
 int compare_person_id(const void *a, const void *b)
 {
    PERSON *A = (PERSON *)a;
    PERSON *B = (PERSON *)b;
    return A->person_id - B->person_id;
 }
 
 int main()
 {
    PERSON Persons[] = {{2, "Bob"}, {3, "Ann"}, {1, "Chris"}};
    qsort(Persons, 3, sizeof(PERSON), compare_person_id);
    printf("%s, %s, %s", Persons[0].person_name, Persons[1].person_name, Persons[2].person_name);
    // 表示結果: "Chris,Bob,Ann"
 }

降順

 // int型の場合
 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]);
    // 表示結果 : "3, 2, 1"
 }

 // 文字列の場合
 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"
 }