0Pricing
C Academy · レッスン

比較関数付き qsort

標準ライブラリのコールバックです。

「比較関数付き qsort」はCoddyKit上の無料C Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

標準ライブラリのqsort

標準ライブラリには、<stdlib.h>で提供されるqsortがあります。これは比較コールバックを使って任意の配列型を扱える汎用ソートです。

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

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

int main(void) {
    int a[] = {3, 1, 2};
    qsort(a, 3, sizeof(int), cmp_int);
    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

qsortのシグネチャ

qsort(base, count, size, compare)は、配列の先頭、要素数、要素サイズ、比較関数を受け取ります。

生のバイト列と利用者が用意した比較関数を使うため、汎用的に利用できます。

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

int cmp(const void *a, const void *b) {
    return *(const int*)a - *(const int*)b;
}

int main(void) {
    int a[] = {9, 4, 7, 1};
    qsort(a, 4, sizeof(int), cmp);
    for (int i = 0; i < 4; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

比較関数の契約

比較関数は、最初の要素を2番目の要素より前に置く場合は負の値、等しい場合は0、後に置く場合は正の値を返します。

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

int cmp(const void *a, const void *b) {
    int x = *(const int*)a, y = *(const int*)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

int main(void) {
    int a[] = {5, 2, 8, 2};
    qsort(a, 4, sizeof(int), cmp);
    for (int i = 0; i < 4; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

voidポインタのキャスト

比較関数は各要素をconst void *として受け取ります。正しい型にキャストし、デリファレンスして値を読み取ってください。

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

int cmp(const void *a, const void *b) {
    double x = *(const double*)a;
    double y = *(const double*)b;
    return (x > y) - (x < y);
}

int main(void) {
    double d[] = {2.5, 1.1, 3.3};
    qsort(d, 3, sizeof(double), cmp);
    printf("%.1f %.1f %.1f\n", d[0], d[1], d[2]);
    return 0;
}

降順

比較結果を逆にすると、大きい値から小さい値の順にソートできます。

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

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

int main(void) {
    int a[] = {1, 5, 3, 2};
    qsort(a, 4, sizeof(int), desc);
    for (int i = 0; i < 4; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

減算によるオーバーフローを避ける

x - yを返すと、大きな整数でオーバーフローする可能性があります。安全な書き方である(x > y) - (x < y)なら、それを避けられます。

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

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

int main(void) {
    int a[] = {100, -100, 0};
    qsort(a, 3, sizeof(int), safe_cmp);
    for (int i = 0; i < 3; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

文字列のソート

char *の配列では、各要素自体がポインタです。そのためconst char * const *にキャストし、strcmpで比較します。

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

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

int main(void) {
    const char *w[] = {"pear", "apple", "fig"};
    qsort(w, 3, sizeof(char*), cmp_str);
    for (int i = 0; i < 3; i++) printf("%s ", w[i]);
    printf("\n");
    return 0;
}

構造体のソート

qsortは構造体の配列にも対応しています。比較関数内で選択したフィールドを比較してください。

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

typedef struct { char name; int age; } Person;

int by_age(const void *a, const void *b) {
    int x = ((const Person*)a)->age;
    int y = ((const Person*)b)->age;
    return (x > y) - (x < y);
}

int main(void) {
    Person p[] = {{'C',30},{'A',20},{'B',25}};
    qsort(p, 3, sizeof(Person), by_age);
    for (int i = 0; i < 3; i++) printf("%c:%d ", p[i].name, p[i].age);
    printf("\n");
    return 0;
}

bsearchも同じ考え方を使う

bsearchは、qsortと同じ契約の比較関数を使って、ソート済み配列を二分探索します。

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

int cmp(const void *a, const void *b) {
    return (*(const int*)a) - (*(const int*)b);
}

int main(void) {
    int a[] = {1, 3, 5, 7, 9};
    int key = 7;
    int *found = bsearch(&key, a, 5, sizeof(int), cmp);
    printf("found: %d\n", found ? *found : -1);
    return 0;
}

複数のソートキー

比較関数では、主キーを比較し、主キーが同じ場合は副キーを比較できます。

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

typedef struct { int grade; int id; } Rec;

int cmp(const void *a, const void *b) {
    const Rec *x = a, *y = b;
    if (x->grade != y->grade) return x->grade - y->grade;
    return x->id - y->id;
}

int main(void) {
    Rec r[] = {{90,2},{90,1},{80,3}};
    qsort(r, 3, sizeof(Rec), cmp);
    for (int i = 0; i < 3; i++) printf("%d/%d ", r[i].grade, r[i].id);
    printf("\n");
    return 0;
}

汎用ソートが重要な理由

qsortはアルゴリズムと比較処理を分離するため、比較可能な任意のデータ型を、十分にテストした1つの関数でソートできます。

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

int cmp(const void *a, const void *b) {
    char x = *(const char*)a, y = *(const char*)b;
    return (x > y) - (x < y);
}

int main(void) {
    char s[] = "dcba";
    qsort(s, 4, sizeof(char), cmp);
    printf("%s\n", s);
    return 0;
}

理解度チェック

qsortの比較関数についての理解度を確認しましょう。

まとめ

比較関数を使ったqsortの利用方法を学びました。

  • qsort(base, count, size, compare)は、任意の配列を汎用的にソートします。
  • 比較関数は2つのconst void *を受け取り、負の値、0、または正の値を返します。
  • オーバーフローを避けるには(x > y) - (x < y)を使います。
  • 同じ比較関数の契約が、bsearch、構造体のソート、複数キーのソートにも使われます。

よくある質問

「比較関数付き qsort」レッスンは無料ですか？

はい。「比較関数付き qsort」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「比較関数付き qsort」で何を学びますか？

標準ライブラリのコールバックです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「比較関数付き qsort」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 関数ポインターの宣言
  2. 関数の受け渡し
  3. 比較関数付き qsort
  4. 関数ポインターテーブル
← C Academyに戻る