6日でできる 新C言語入門｜C言語の比較関数と文字列ソート

6日でできる 新C言語入門｜C言語の比較関数と文字列ソート

並び順を決めるのは、比較関数の返す値。
strcmpとqsortを組み合わせて、C言語で文字列や構造体を自在に並べ替えよう。

C言語で配列を並べ替えるとき、数値の大小だけでなく、文字列を辞書順に並べたい場面があります。

たとえば、単語一覧をアルファベット順に並べる、商品名を名前順に表示する、学生データを氏名順に整列する、といった処理です。このような文字列の並べ替えでは、単純な大小比較ではなく、文字列同士を比較する仕組みが必要になります。

C言語では、文字列の比較にstrcmpを使います。strcmpは、2つの文字列を比べて、どちらが辞書順で前にあるかを判定する関数です。

さらに、標準ライブラリのqsortを使うと、配列の要素を自由な基準で並べ替えられます。ただし、qsortはどのような順番に並べるべきかを自分では判断できません。そのため、比較関数を自分で作り、qsortへ渡します。

この比較関数が、文字列ソートの中心です。

この記事では、strcmpの戻り値の意味、qsortに渡す比較関数の書き方、文字列配列を並べ替えるときのポインタの考え方、構造体配列を特定メンバでソートする方法まで、サンプルプログラムを使ってやさしく解説していきます。

文字列の比較にはstrcmpを使う

C言語では、文字列をそのまま比較演算子で比べることはできません。

たとえば、次のように文字列同士を比較しても、文字列の内容を辞書順で比較しているわけではありません。

if (word1 < word2) {
    ...
}

C言語の文字列は、char配列またはcharへのポインタとして扱われます。
そのため、文字列の内容を比べたい場合は、strcmpを使います。

strcmpを使うには、string.hを読み込みます。

#include <string.h>

strcmpの基本形は次の通りです。

int strcmp(const char* s1, const char* s2);

strcmpは、s1とs2の文字列を先頭から順番に比較し、結果を整数で返します。

たとえば、appleとbananaを比較すると、appleのほうが辞書順で前にあるため、strcmpは負の値を返します。

strcmpの戻り値をqsortの比較関数に使える理由

qsortに渡す比較関数も、2つの要素を比較して、整数を返す形になっています。

qsortの比較関数では、戻り値の意味が次のように決まっています。

このルールは、strcmpの戻り値の考え方と相性がよいです。

文字列を辞書順に並べたい場合、比較関数の中でstrcmpを呼び出し、その戻り値をそのままqsortへ返すことができます。

return strcmp(*a, *b);

これにより、qsortは文字列同士の順序を判断できます。

図：strcmpは文字列の順序を戻り値で伝える

この図から分かること

この図から分かるのは、strcmpが文字列の大小関係を整数の戻り値で表すということです。

負の値なら左の文字列が前、0なら同じ、正の値なら左の文字列が後ろという意味になります。この戻り値のルールはqsortの比較関数と相性がよく、文字列配列を辞書順に並べるときにそのまま活用できます。

qsortに比較関数を渡す考え方

qsortは、C言語の標準ライブラリに用意されている汎用的なソート関数です。

qsortを使うには、stdlib.hを読み込みます。

#include <stdlib.h>

qsortの基本形は次のようになっています。

void qsort(
    void* base,
    size_t num,
    size_t size,
    int (*compare)(const void*, const void*)
);

それぞれの引数の意味は次の通りです。

qsortは、配列の中身が整数なのか、文字列なのか、構造体なのかを知りません。
そのため、どの要素を前に置くべきかは、比較関数で決めます。

比較関数は、qsortから2つの要素を受け取り、戻り値で順序を伝えます。

int compare(const void* a, const void* b)

qsortでは、どの型の配列でも扱えるように、比較関数の引数はconst void*になっています。
そのため、比較関数の中で目的の型へ変換してから比較します。

文字列配列をqsortで扱うときの注意

文字列配列をqsortで並べ替える場合、ポインタの考え方が少し重要になります。

たとえば、次のような文字列配列があるとします。

char* words[SIZE] = {
    "orange",
    "apple",
    "banana",
    "grape",
    "lemon"
};

この配列の1要素は、char*です。
つまり、words[0]、words[1]、words[2]は、それぞれ文字列の先頭を指すポインタです。

qsortの比較関数には、配列要素そのものではなく、配列要素のアドレスが渡されます。

文字列配列の場合、配列要素はchar*なので、そのアドレスはchar**として考えられます。

そのため、文字列比較関数では、const voidをconst char**として扱い、さらにを付けて実際の文字列を取り出します。

const char* const* leftWord = (const char* const*)left;
const char* const* rightWord = (const char* const*)right;
return strcmp(*leftWord, *rightWord);

この部分は最初に難しく見えやすいですが、qsortから渡されるのは配列要素のアドレスである、と考えると整理しやすくなります。

文字列配列を辞書順にソートするプログラム

次のプログラムでは、英単語の文字列配列をqsortで辞書順に並べ替えます。

プロジェクト/ファイル名： Lesson72_1/main.c

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

#define SIZE 5

int compareString(const void*, const void*);
void show(char*[], int);

int main(void) {
    char* words[SIZE] = {
        "orange",
        "apple",
        "banana",
        "grape",
        "lemon"
    };

    printf("初期配列: ");
    show(words, SIZE);

    // qsortで文字列配列を辞書順に並べ替える
    qsort(words, SIZE, sizeof(char*), compareString);

    printf("ソート後: ");
    show(words, SIZE);

    return 0;
}

// qsortに渡す文字列用の比較関数
int compareString(const void* left, const void* right) {
    const char* const* leftWord = (const char* const*)left;
    const char* const* rightWord = (const char* const*)right;

    return strcmp(*leftWord, *rightWord);
}

// 文字列配列の内容を表示する関数
void show(char* array[], int size) {
    int i;

    for (i = 0; i < size; i++) {
        printf("%s ", array[i]);
    }

    printf("\n");
}

実行結果

初期配列: orange apple banana grape lemon
ソート後: apple banana grape lemon orange

このプログラムでは、words配列に5つの文字列を入れています。

char* words[SIZE] = {
    "orange",
    "apple",
    "banana",
    "grape",
    "lemon"
};

qsortでは、words配列を並べ替えています。

qsort(words, SIZE, sizeof(char*), compareString);

第1引数のwordsは、並べ替えたい配列の先頭です。
第2引数のSIZEは、配列の要素数です。
第3引数のsizeof(char*)は、1要素のサイズです。
第4引数のcompareStringは、文字列の並び順を決める比較関数です。

compareString関数の中身を詳しく見る

compareString関数は、qsortから渡された2つの要素を文字列として比較します。

int compareString(const void* left, const void* right)

leftとrightはconst void*型です。
そのままでは文字列として扱えないため、文字列ポインタのアドレスとして変換します。

const char* const* leftWord = (const char* const*)left;
const char* const* rightWord = (const char* const*)right;

leftWordとrightWordは、文字列を指すポインタのアドレスを表しています。
そのため、leftWordとrightWordで、実際の文字列を取り出せます。

return strcmp(*leftWord, *rightWord);

このstrcmpの結果をそのまま返すことで、qsortに並び順を伝えています。

sizeof(char*)を指定する理由

文字列配列をqsortで並べ替えるとき、1要素のサイズにはsizeof(char*)を指定します。

qsort(words, SIZE, sizeof(char*), compareString);

これは、words配列の1要素がchar*だからです。

文字列そのものの長さを指定するわけではありません。
words配列は文字列ポインタの配列なので、1要素はポインタ1個分です。

より配列の形に合わせて書くなら、次のようにsizeof(words[0])を使うこともできます。

qsort(words, SIZE, sizeof(words[0]), compareString);

この書き方なら、配列要素の型が変わったときにも対応しやすくなります。

図：文字列配列ではqsortから文字列ポインタのアドレスが渡る

この図から分かること

この図から分かるのは、文字列配列をqsortで扱うとき、比較関数には文字列そのものではなく、配列要素のアドレスが渡るということです。

wordsの各要素はchar*で、文字列を指しています。qsortはその要素のアドレスをcompareStringへ渡すため、比較関数の中ではconst char**として受け取り、*leftWordのようにして実際の文字列を取り出します。

日本語文字列をソートするときの注意

strcmpは、文字コード上の並びで文字列を比較します。

そのため、日本語文字列をstrcmpで並べ替えた場合、五十音順のような自然な日本語順になるとは限りません。実行環境、文字コード、ロケールの設定によって見え方が変わる場合があります。

英単語の辞書順のような学習では、strcmpの動きを確認しやすいです。
日本語の自然な並び順を実現したい場合は、ロケールや文字コード、専用の比較処理について別途考える必要があります。

構造体配列もqsortで並べ替えられる

qsortは文字列配列だけでなく、構造体配列にも使えます。

たとえば、次のような構造体があるとします。

typedef struct {
    int id;
    char name[32];
    int score;
} Member;

このMember配列を、nameメンバの辞書順で並べ替えることができます。

構造体配列の場合、qsortの比較関数には、構造体要素のアドレスが渡されます。

文字列配列では、配列要素がcharだったため、比較関数内ではconst char**として扱いました。
一方、構造体配列では、配列要素そのものがMember型なので、比較関数内ではconst Memberとして扱います。

構造体のnameメンバでソートするプログラム

次のプログラムでは、会員データの構造体配列をnameメンバの辞書順で並べ替えます。

プロジェクト/ファイル名： Lesson72_2/main.c

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

typedef struct {
    int id;
    char name[32];
    int point;
} Member;

int compareByName(const void*, const void*);
void show(Member*, int);

int main(void) {
    Member members[] = {
        { 3, "Sato", 120 },
        { 1, "Tanaka", 300 },
        { 2, "Aoki", 250 },
        { 5, "Kato", 180 },
        { 4, "Suzuki", 220 }
    };

    int size = sizeof(members) / sizeof(members[0]);

    printf("ソート前:\n");
    show(members, size);

    // nameメンバを基準にqsortで並べ替える
    qsort(members, size, sizeof(Member), compareByName);

    printf("ソート後:\n");
    show(members, size);

    return 0;
}

// 構造体のnameメンバを比較する関数
int compareByName(const void* left, const void* right) {
    const Member* leftMember = (const Member*)left;
    const Member* rightMember = (const Member*)right;

    return strcmp(leftMember->name, rightMember->name);
}

// 構造体配列の内容を表示する関数
void show(Member* array, int size) {
    int i;

    for (i = 0; i < size; i++) {
        printf("ID:%d 名前:%s ポイント:%d\n",
            array[i].id, array[i].name, array[i].point);
    }
}

実行結果

ソート前:
ID:3 名前:Sato ポイント:120
ID:1 名前:Tanaka ポイント:300
ID:2 名前:Aoki ポイント:250
ID:5 名前:Kato ポイント:180
ID:4 名前:Suzuki ポイント:220
ソート後:
ID:2 名前:Aoki ポイント:250
ID:5 名前:Kato ポイント:180
ID:3 名前:Sato ポイント:120
ID:4 名前:Suzuki ポイント:220
ID:1 名前:Tanaka ポイント:300

このプログラムでは、Member型の配列membersを作っています。

Member members[] = {
    { 3, "Sato", 120 },
    { 1, "Tanaka", 300 },
    { 2, "Aoki", 250 },
    { 5, "Kato", 180 },
    { 4, "Suzuki", 220 }
};

qsortでは、members配列を並べ替えています。

qsort(members, size, sizeof(Member), compareByName);

1要素のサイズにはsizeof(Member)を指定しています。
members配列の1要素がMember型だからです。

compareByName関数の中身を詳しく見る

compareByName関数では、qsortから渡された2つの要素をMember型のポインタとして扱っています。

const Member* leftMember = (const Member*)left;
const Member* rightMember = (const Member*)right;

leftとrightはconst void型ですが、実際にはMember型要素のアドレスです。
そのため、const Memberに変換します。

そして、nameメンバをstrcmpで比較しています。

return strcmp(leftMember->name, rightMember->name);

構造体ポインタからメンバへアクセスしているため、->を使います。

このように、構造体配列をqsortで並べ替える場合は、比較関数の中で並べ替え基準にしたいメンバを取り出して比較します。

図：構造体配列は比較したいメンバを取り出して並べ替える

この図から分かること

この図から分かるのは、構造体配列をqsortでソートするときは、比較関数の中で並べ替えの基準にしたいメンバを取り出すということです。

Member配列の要素は構造体なので、比較関数ではconst Member*として受け取ります。そのあと、nameメンバをstrcmpで比較することで、会員データ全体を名前順に並べ替えられます。

文字列配列と構造体配列で比較関数の型が違う理由

文字列配列と構造体配列では、qsortの比較関数で扱う型が違います。

理由は、配列の1要素の型が違うからです。

文字列配列では、1要素がcharです。
qsortから渡されるのは、そのchar要素のアドレスです。
そのため、const char**として扱います。

構造体配列では、1要素がMemberです。
qsortから渡されるのは、そのMember要素のアドレスです。
そのため、const Member*として扱います。

この違いを理解しておくと、qsortの比較関数が読みやすくなります。

比較関数で降順にするには

比較関数の戻り値を逆にすると、降順にできます。

たとえば、文字列を逆順にしたい場合は、strcmpの引数の順番を入れ替えます。

return strcmp(*rightWord, *leftWord);

構造体のnameメンバを逆順にしたい場合も、引数の順番を逆にできます。

return strcmp(rightMember->name, leftMember->name);

数値のメンバで降順にしたい場合は、大きい値を前に置くように比較します。

if (leftMember->point > rightMember->point) {
    return -1;
}
if (leftMember->point < rightMember->point) {
    return 1;
}
return 0;

比較関数は、どちらの要素を前に置きたいかをqsortへ伝えるための関数です。
戻り値のルールを理解すると、昇順、降順、特定メンバ順などを自由に作れます。

qsortの比較関数を書くときの注意点

qsortの比較関数を書くときは、次の点に注意しましょう。

引数の型はconst void*に合わせる

qsortに渡す比較関数は、次の形に合わせます。

int compare(const void*, const void*);

比較対象の型がintでも、charでも、構造体でも、qsortからはconst voidとして渡されます。
比較関数の中で、正しい型へ変換してから比較します。

文字列比較にはstrcmpを使う

文字列の内容を比較したい場合は、strcmpを使います。

文字列ポインタ同士を比較演算子で比べても、文字列の内容比較にはなりません。

配列要素の型を意識する

qsortでは、比較関数に配列要素のアドレスが渡されます。

そのため、文字列配列ではconst char**、構造体配列ではconst Member*というように、配列要素の型に合わせて考える必要があります。

比較関数でデータを書き換えない

比較関数は、順序を決めるための関数です。
基本的には、比較対象のデータを書き換えないようにします。

引数がconst void*になっているのも、比較だけを行う意図があるためです。

日本語の自然順には注意する

strcmpは文字コード順に比較します。
そのため、日本語の五十音順とは異なる並びになることがあります。

日本語の自然な順序が必要な場合は、文字コードやロケール、専用の比較ルールを検討する必要があります。

比較関数を理解するとソートの応用が広がる

qsortの強みは、比較関数を変えるだけで、さまざまな並べ替えができることです。

比較関数は、qsortに並び替えのルールを伝える役割を持っています。

つまり、qsortは並べ替えの作業を担当し、比較関数は並び順の判断を担当します。

この分担を理解すると、C言語で扱えるソート処理が大きく広がります。

文字列ソートはポインタ理解にもつながる

文字列配列のqsortは、ポインタの理解にもつながります。

char*の配列では、配列の要素そのものがポインタです。
qsortの比較関数には、その要素のアドレスが渡されます。
そのため、比較関数の中ではconst char**として扱い、*を使って実際の文字列を取り出します。

一方、構造体配列では、配列の要素は構造体そのものです。
比較関数には構造体要素のアドレスが渡されるため、const Member*として扱います。

この違いは、C言語の配列、ポインタ、構造体、関数ポインタがつながる大切なポイントです。

Lesson72_1では、文字列配列をqsortとstrcmpで辞書順に並べ替えました。
Lesson72_2では、構造体配列をnameメンバの辞書順で並べ替えました。

比較関数を自分で書けるようになると、単純な数値ソートだけでなく、文字列や構造体を目的に合わせて並べ替えられるようになります。
文字列ソートを通して、qsortと比較関数の関係、そしてポインタの扱いをしっかり身につけていきましょう。