C 言語の qsort() について

はじめに

昔から qsort() がいまいちよくわかっていなかったので勉強しなおしました。

qsort 関数とは

qsort 関数は stdlib.h に保存されています。

#include <stdlib.h>

void qsort(
    void *base, 
    size_t number, 
    size_t size, 
    int (*comparison_function)(const void *n1, const void *n2)
);

引数

• base：ソート対象の配列のポインタ
• number：配列の長さ
• size：配列の要素のバイト単位の長さ。例えば int 配列なら sizeof(int) を指定する。
• comparison_function：比較関数のポインタ。n1 が n2 より前、等しい、後ろの場合にそれぞれ負の値、0、正の値を返す必要がある。

単純な配列のソート

#include <stdio.h>
#include <stdlib.h>
#define N 10

int comp_ints(const void *vxp, const void *vyp)
{
    int* xp = (int*) vxp;
    int* yp = (int*) vyp;
    return *xp - *yp;  
}

int main(void)
{
    int i, array[N] = {5, 9, 2, 7, 4, 0, 8, 1, 6, 3};

    qsort(array, N, sizeof(int), comp_ints);

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

    return 0;
}

qsort 関数は実装時点では比較対象の構造が決まっていないので、比較関数へ渡すポインタ vxp vypは void 型である。そのためこれを int 型のポインタへキャストする必要がある。それが、xp yp である。

0 1 2 3 4 5 6 7 8 9

構造体のソート

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 5

// 生徒構造体
typedef struct {
    int roll_no; // 出席番号
    char name[50]; // 氏名
} Student;

// 比較関数（出席番号順にソート）
int comp_roll_no(const void* vxp, const void* vyp)
{
    Student* xp = (Student*) vxp;
    Student* yp = (Student*) vyp;
    return xp->roll_no - yp->roll_no;
}

int main()
{
    Student students[N] = {
        {5, "Alice"},
        {3, "Bob"},
        {1, "Charlie"},
        {4, "Diana"},
        {2, "Eve"}
    };
    int i;

    printf("ソート前:\n");
    for(i = 0; i < 5; i++) {
        printf("出席番号: %d,\t氏名: %s\n", students[i].roll_no, students[i].name);
    }

    qsort(students, N, sizeof(Student), comp_roll_no);

    printf("\nソート後:\n");
    for(i = 0; i < N; i++) {
        printf("出席番号: %d,\t氏名: %s\n", students[i].roll_no, students[i].name);
    }

    return 0;
}

アロー演算 xp->roll_no は、(*xp).roll_no と等価である。

ソート前:
出席番号: 5,    氏名: Alice
出席番号: 3,    氏名: Bob
出席番号: 1,    氏名: Charlie
出席番号: 4,    氏名: Diana
出席番号: 2,    氏名: Eve

ソート後:
出席番号: 1,    氏名: Charlie
出席番号: 2,    氏名: Eve
出席番号: 3,    氏名: Bob
出席番号: 4,    氏名: Diana
出席番号: 5,    氏名: Alice