[C言語] 標準ライブラリのクイックソート(qsort)の使い方

2025-04-14更新日: 2025-04-14

C言語の標準ライブラリには、配列を効率的にソートするための関数としてqsortがあります。

qsortは、クイックソートアルゴリズムを基にした汎用的なソート関数で、配列の要素数、要素のサイズ、比較関数を引数として受け取ります。

比較関数は、2つの要素を比較し、負の値、0、正の値を返すことで、要素の順序を決定します。

この関数を使用することで、整数や文字列など、さまざまなデータ型の配列を簡単にソートすることが可能です。

目次から探す

qsort関数の概要

C言語の標準ライブラリには、配列を効率的にソートするための関数としてqsortがあります。

この関数は、クイックソートアルゴリズムを基にしており、一般的に高速であることが特徴です。

qsortは、任意のデータ型の配列をソートすることができ、ユーザーが定義した比較関数を使用して、要素間の順序を決定します。

これにより、整数や文字列、構造体など、さまざまなデータ型の配列を柔軟にソートすることが可能です。

qsortを使用することで、手動でソートアルゴリズムを実装する手間を省き、コードの可読性と保守性を向上させることができます。

qsort関数のシグネチャと引数

qsortのシグネチャ

qsort関数は、C言語の標準ライブラリに含まれており、以下のシグネチャを持っています。

#include <stdlib.h>
void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));

このシグネチャからわかるように、qsortは4つの引数を取ります。

それぞれの引数は、ソートする配列やその要素に関する情報を提供します。

各引数の役割

配列のポインタ

役割: ソート対象となる配列の先頭を指すポインタです。
型: void *
説明: 配列のデータ型に依存せず、任意のデータ型の配列を扱うことができます。

このポインタは、配列の最初の要素を指します。

配列の要素数

役割: 配列内の要素の数を指定します。
型: size_t
説明: 配列の要素数を指定することで、qsortはどの範囲をソートするかを認識します。

要素のサイズ

役割: 配列の各要素のサイズをバイト単位で指定します。
型: size_t
説明: 各要素のサイズを指定することで、qsortはメモリ上での要素の位置を正しく計算し、ソートを行います。

比較関数のポインタ

役割: 要素間の順序を決定するための比較関数を指すポインタです。
型: int (*compar)(const void *, const void *)
説明: この関数は、2つの要素を比較し、第一引数が第二引数より小さい場合は負の値、等しい場合は0、大きい場合は正の値を返します。

これにより、qsortは要素を適切に並べ替えることができます。

比較関数の実装

比較関数の基本

qsort関数を使用する際には、要素間の順序を決定するための比較関数をユーザーが実装する必要があります。

この関数は、2つの要素を引数として受け取り、それらの順序を示す整数を返します。

具体的には、第一引数が第二引数より小さい場合は負の値、等しい場合は0、大きい場合は正の値を返すように実装します。

比較関数の書き方

比較関数は、以下のようなシグネチャで実装します。

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

この関数は、voidポインタを受け取るため、実際のデータ型にキャストしてから比較を行います。

これにより、任意のデータ型に対応した比較が可能になります。

比較関数の例

整数のソート

整数配列をソートするための比較関数の例です。

int compareInts(const void *a, const void *b) {
    // ポインタを整数型にキャストして値を取得
    int intA = *(int *)a;
    int intB = *(int *)b;
    return (intA > intB) - (intA < intB);
}

この関数は、整数の大小を比較し、その結果を返します。

文字列のソート

文字列配列をソートするための比較関数の例です。

#include <string.h>
int compareStrings(const void *a, const void *b) {
    // ポインタを文字列型にキャストして比較
    return strcmp(*(const char **)a, *(const char **)b);
}

strcmp関数を使用して、文字列の辞書順を比較します。

構造体のソート

構造体配列をソートするための比較関数の例です。

ここでは、構造体のメンバであるageを基にソートします。

typedef struct {
    char name[50];
    int age;
} Person;
int comparePersons(const void *a, const void *b) {
    // ポインタを構造体型にキャストしてメンバを比較
    int ageA = ((Person *)a)->age;
    int ageB = ((Person *)b)->age;
    return (ageA > ageB) - (ageA < ageB);
}

この関数は、Person構造体のageメンバを基に比較を行い、年齢順にソートします。

qsortの実用例

整数配列のソート

以下は、整数配列をqsortを使ってソートする例です。

#include <stdio.h>
#include <stdlib.h>
// 比較関数
int compareInts(const void *a, const void *b) {
    int intA = *(int *)a;
    int intB = *(int *)b;
    return (intA > intB) - (intA < intB);
}
int main() {
    int numbers[] = {5, 3, 8, 6, 2};
    size_t numElements = sizeof(numbers) / sizeof(numbers[0]);
    // qsortを使用してソート
    qsort(numbers, numElements, sizeof(int), compareInts);
    // 結果を表示
    for (size_t i = 0; i < numElements; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

2 3 5 6 8

このプログラムは、整数配列を昇順にソートし、結果を表示します。

文字列配列のソート

次に、文字列配列をqsortでソートする例です。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 比較関数
int compareStrings(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}
int main() {
    const char *fruits[] = {"banana", "apple", "orange", "grape"};
    size_t numElements = sizeof(fruits) / sizeof(fruits[0]);
    // qsortを使用してソート
    qsort(fruits, numElements, sizeof(char *), compareStrings);
    // 結果を表示
    for (size_t i = 0; i < numElements; i++) {
        printf("%s ", fruits[i]);
    }
    return 0;
}

apple banana grape orange

このプログラムは、文字列配列を辞書順にソートし、結果を表示します。

構造体配列のソート

最後に、構造体配列をqsortでソートする例です。

#include <stdio.h>
#include <stdlib.h>
// Person構造体の定義
typedef struct {
    char name[50];
    int age;
} Person;
// 比較関数
int comparePersons(const void *a, const void *b) {
    int ageA = ((Person *)a)->age;
    int ageB = ((Person *)b)->age;
    return (ageA > ageB) - (ageA < ageB);
}
int main() {
    Person people[] = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    size_t numElements = sizeof(people) / sizeof(people[0]);
    // qsortを使用してソート
    qsort(people, numElements, sizeof(Person), comparePersons);
    // 結果を表示
    for (size_t i = 0; i < numElements; i++) {
        printf("%s: %d\n", people[i].name, people[i].age);
    }
    return 0;
}

Bob: 25
Alice: 30
Charlie: 35

このプログラムは、Person構造体のageメンバを基に、構造体配列を年齢順にソートし、結果を表示します。

qsortの応用

カスタムデータ型のソート

qsortは、カスタムデータ型の配列をソートする際にも非常に便利です。

例えば、以下のようなカスタムデータ型を持つ配列をソートすることができます。

#include <stdio.h>
#include <stdlib.h>
// カスタムデータ型の定義
typedef struct {
    char title[100];
    int pages;
} Book;
// 比較関数
int compareBooks(const void *a, const void *b) {
    int pagesA = ((Book *)a)->pages;
    int pagesB = ((Book *)b)->pages;
    return (pagesA > pagesB) - (pagesA < pagesB);
}
int main() {
    Book library[] = {{"C Programming", 300}, {"Algorithms", 500}, {"Data Structures", 400}};
    size_t numElements = sizeof(library) / sizeof(library[0]);
    // qsortを使用してソート
    qsort(library, numElements, sizeof(Book), compareBooks);
    // 結果を表示
    for (size_t i = 0; i < numElements; i++) {
        printf("%s: %d pages\n", library[i].title, library[i].pages);
    }
    return 0;
}

このプログラムは、Book構造体のpagesメンバを基に、書籍をページ数順にソートします。

降順ソートの実装

qsortを使用して降順にソートするには、比較関数の戻り値を逆にするだけです。

以下は、整数配列を降順にソートする例です。

#include <stdio.h>
#include <stdlib.h>
// 比較関数(降順)
int compareIntsDesc(const void *a, const void *b) {
    int intA = *(int *)a;
    int intB = *(int *)b;
    return (intB > intA) - (intB < intA);
}
int main() {
    int numbers[] = {5, 3, 8, 6, 2};
    size_t numElements = sizeof(numbers) / sizeof(numbers[0]);
    // qsortを使用して降順にソート
    qsort(numbers, numElements, sizeof(int), compareIntsDesc);
    // 結果を表示
    for (size_t i = 0; i < numElements; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

8 6 5 3 2

このプログラムは、整数配列を降順にソートし、結果を表示します。

部分的なソートの実現

qsortを使用して配列の一部だけをソートすることも可能です。

以下は、配列の一部をソートする例です。

#include <stdio.h>
#include <stdlib.h>
// 比較関数
int compareInts(const void *a, const void *b) {
    int intA = *(int *)a;
    int intB = *(int *)b;
    return (intA > intB) - (intA < intB);
}
int main() {
    int numbers[] = {5, 3, 8, 6, 2, 7, 4};
    size_t start = 2; // ソート開始位置
    size_t end = 5;   // ソート終了位置
    size_t numElements = end - start + 1;
    // 部分的にqsortを使用してソート
    qsort(&numbers[start], numElements, sizeof(int), compareInts);
    // 結果を表示
    for (size_t i = 0; i < sizeof(numbers) / sizeof(numbers[0]); i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}