qsortとbsearch ― 比較関数を渡して並べ替え・検索する

導入

配列の並べ替え（ソート）を毎回自分でアルゴリズムから書くのは大変です。標準ライブラリの qsort を使えば、「2つの要素をどう比べるか」という比較関数だけ教えれば、あとはライブラリ側が任意の型の配列を並べ替えてくれます。

説明

qsort は <stdlib.h> にあります。4つの引数を渡します。

qsort(配列, 要素数, 要素1つのサイズ, 比較関数);

比較関数は int compare(const void *a, const void *b) という決まった形で書きます。a が b より小さければ負の数、大きければ正の数、等しければ 0 を返すのがルールです。void * は「型を問わない汎用ポインタ」で、実際の型にキャスト（型変換）してから使います。

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

int compare_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return x - y;   // 昇順（小さい順）
}

int main(void) {
    int nums[] = { 5, 2, 8, 1, 9, 3 };
    int n = sizeof(nums) / sizeof(nums[0]);

    qsort(nums, n, sizeof(int), compare_int);

    for (int i = 0; i < n; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    return 0;
}

sizeof(nums) / sizeof(nums[0])（配列全体のバイト数 ÷ 要素1つのバイト数）は、配列の要素数を求める定番の書き方です。compare_int の中では、受け取った void * を const int * にキャストしてから * で値を取り出しています。

並べ替え済みの配列であれば、bsearch（二分探索）で高速に検索できます。見つかった要素へのポインタ、見つからなければ NULL を返します。

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

int compare_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return x - y;
}

int main(void) {
    int nums[] = { 1, 2, 3, 5, 8, 9 };  // あらかじめソート済みであること
    int n = sizeof(nums) / sizeof(nums[0]);
    int key = 8;

    int *found = bsearch(&key, nums, n, sizeof(int), compare_int);
    if (found != NULL) {
        printf("見つかった: %d\n", *found);
    } else {
        printf("見つからない\n");
    }
    return 0;
}

比較関数を書き換えるだけで、int 以外の配列も並べ替えられます。次は文字列（char *）の配列を strcmp を使って並べ替える例です。

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

int compare_str(const void *a, const void *b) {
    const char *sa = *(const char **)a;
    const char *sb = *(const char **)b;
    return strcmp(sa, sb);
}

int main(void) {
    const char *names[] = { "Taro", "Hanako", "Jiro" };
    int n = sizeof(names) / sizeof(names[0]);

    qsort(names, n, sizeof(char *), compare_str);

    for (int i = 0; i < n; i++) {
        printf("%s\n", names[i]);
    }
    return 0;
}

qsort 本体は「int を並べる」とも「文字列を並べる」とも知りません。渡された比較関数の返す値だけを見て順番を決めているので、比較関数を差し替えるだけでどんな型にも対応できるのです。

やってみよう

compare_int の return x - y; を return y - x; に変えて、降順（大きい順）に並び替わることを確かめましょう。bsearch の key を配列に存在しない値に変えて 見つからない になることも確認してください。

演習

降順に並べ替える比較関数 compare_desc を書き、int nums[] = {5, 2, 8, 1, 9, 3}; を qsort で降順に並べ替えて表示してください（結果は 9 8 5 3 2 1）。