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

2023-09-102024-06-03

この記事では、C言語の標準ライブラリに含まれるqsort関数について学びます。

qsort関数は、配列を効率的にソートするための便利な関数です。

この記事を読むことで、qsort関数の基本的な使い方や、さまざまなデータ型の配列をソートする方法、さらには応用的な使い方まで理解できるようになります。

目次から探す

qsort関数とは

qsort関数の概要

C言語の標準ライブラリには、配列を効率的にソートするための関数がいくつか含まれています。

その中でも特に有名で広く使われているのがqsort関数です。

qsortは「クイックソート(Quick Sort)」の略で、その名の通りクイックソートアルゴリズムを用いて配列をソートします。

クイックソートは、分割統治法を用いた非常に効率的なソートアルゴリズムで、平均的な時間計算量はO(n log n)です。

qsort関数はこのアルゴリズムを内部で使用し、汎用的なソート機能を提供します。

qsort関数の用途

qsort関数は、以下のような用途で広く利用されています。

整数配列のソート:

数値データを昇順または降順に並べ替える際に使用されます。

例えば、学生の成績をソートする場合などに便利です。

文字列配列のソート:

文字列データをアルファベット順に並べ替える際に使用されます。

例えば、辞書の単語リストをソートする場合などに役立ちます。

構造体配列のソート:

カスタムデータ型(構造体)を特定のフィールドに基づいてソートする際に使用されます。

例えば、社員データを年齢順や給与順にソートする場合などに利用されます。

汎用的なデータのソート:

任意のデータ型をソートするために使用できます。

qsort関数は、比較関数をユーザーが定義することで、どのようなデータ型でもソート可能です。

このように、qsort関数は非常に汎用性が高く、さまざまな場面で利用されています。

次のセクションでは、qsort関数の基本的な使い方について詳しく解説します。

qsort関数の基本的な使い方

qsort関数のシグネチャ

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

qsort関数のシグネチャは以下のようになっています。

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

このシグネチャを理解することが、qsort関数を正しく使うための第一歩です。

qsort関数の引数の説明

qsort関数は4つの引数を取ります。

それぞれの引数について詳しく見ていきましょう。

配列のポインタ

最初の引数 base は、ソート対象となる配列の先頭を指すポインタです。

このポインタは void* 型であり、任意のデータ型の配列を指すことができます。

例えば、整数型の配列や文字列型の配列など、様々なデータ型の配列をソートすることができます。

配列の要素数

2番目の引数 nmemb は、配列の要素数を示す size_t 型の値です。

この値は、配列の全要素数を指定する必要があります。

例えば、10個の整数が格納されている配列をソートする場合、この引数には10を指定します。

要素のサイズ

3番目の引数 size は、配列の各要素のサイズを示す size_t 型の値です。

この値は、各要素のバイト数を指定します。

例えば、整数型の配列の場合、各要素のサイズは sizeof(int) となります。

比較関数のポインタ

最後の引数 compar は、2つの要素を比較するための関数へのポインタです。

この関数は、2つの要素を引数として受け取り、それらの比較結果を整数値で返します。

具体的には、以下のようなシグネチャを持つ関数を指定します。

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

この関数は、a が b より小さい場合は負の値、等しい場合は0、大きい場合は正の値を返す必要があります。

これにより、qsort関数は配列の要素を適切に比較し、ソートを行います。

次に、具体的な比較関数の実装方法について見ていきましょう。

比較関数の実装

比較関数の基本構造

qsort関数を使用する際に最も重要な要素の一つが「比較関数」です。

比較関数は、qsortが要素を比較するために使用する関数で、2つの要素を引数として受け取り、それらの順序を決定します。

比較関数は以下のようなシグネチャを持ちます。

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

この関数は、以下のような値を返す必要があります。

条件	結果
a < b	負の値
a > b	正の値
a == b	0

整数配列のソート

整数配列をソートするための比較関数の実装例を見てみましょう。

以下のコードは、整数配列を昇順にソートするための比較関数です。

int compare_int(const void *a, const void *b) {
    int int_a = *(int*)a;
    int int_b = *(int*)b;
    if (int_a < int_b) return -1;
    else if (int_a > int_b) return 1;
    else return 0;
}

この関数は、qsort関数に渡すことで、整数配列を昇順にソートすることができます。

文字列配列のソート

次に、文字列配列をソートするための比較関数を見てみましょう。

文字列はcharの配列であり、strcmp関数を使用して比較することが一般的です。

int compare_string(const void *a, const void *b) {
    const char **str_a = (const char **)a;
    const char **str_b = (const char **)b;
    return strcmp(*str_a, *str_b);
}

この関数を使用することで、文字列配列をアルファベット順にソートすることができます。

構造体配列のソート

最後に、構造体配列をソートするための比較関数を見てみましょう。

例えば、以下のような構造体を持つ配列をソートする場合を考えます。

typedef struct {
    int id;
    char name[50];
} Person;

この構造体配列をidの昇順でソートするための比較関数は以下のようになります。

int compare_person(const void *a, const void *b) {
    Person *person_a = (Person *)a;
    Person *person_b = (Person *)b;
    return (person_a->id - person_b->id);
}

また、nameのアルファベット順でソートする場合は以下のようになります。

int compare_person_name(const void *a, const void *b) {
    Person *person_a = (Person *)a;
    Person *person_b = (Person *)b;
    return strcmp(person_a->name, person_b->name);
}

これらの比較関数を使用することで、構造体配列を任意のフィールドでソートすることができます。

qsort関数の具体例

ここでは、qsort関数を使った具体的なソートの例をいくつか紹介します。

これにより、qsort関数の使い方がより明確になるでしょう。

整数配列のソート例

まずは、整数配列をソートする例を見てみましょう。

以下のコードでは、整数配列を昇順にソートします。

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

このコードを実行すると、以下のような結果が得られます。

1 2 5 5 6 9

文字列配列のソート例

次に、文字列配列をソートする例を見てみましょう。

以下のコードでは、文字列配列をアルファベット順にソートします。

#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 *arr[] = {"banana", "apple", "cherry", "date"};
    int n = sizeof(arr) / sizeof(arr[0]);
    // qsort関数を使用してソート
    qsort(arr, n, sizeof(const char *), compareStrings);
    // ソート結果を表示
    for(int i = 0; i < n; i++) {
        printf("%s ", arr[i]);
    }
    return 0;
}

このコードを実行すると、以下のような結果が得られます。

apple banana cherry date

構造体配列のソート例

最後に、構造体配列をソートする例を見てみましょう。

以下のコードでは、構造体配列を特定のメンバ変数に基づいてソートします。

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

このコードを実行すると、以下のような結果が得られます。

Bob: 25
Alice: 30
Charlie: 35

これらの例を通じて、qsort関数の使い方が理解できたでしょう。

qsort関数は非常に強力で、さまざまなデータ型の配列を簡単にソートすることができます。

qsort関数の応用

昇順と降順のソート

qsort関数を使って配列をソートする際、昇順と降順の両方でソートすることができます。

これは比較関数の実装を変更することで実現できます。

昇順ソートの比較関数

以下は整数配列を昇順にソートするための比較関数の例です。

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

降順ソートの比較関数

次に、整数配列を降順にソートするための比較関数の例です。

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

実行例

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

#include <stdio.h>
#include <stdlib.h>
int compare_asc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
int compare_desc(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}
int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    size_t arr_size = sizeof(arr) / sizeof(arr[0]);
    // 昇順ソート
    qsort(arr, arr_size, sizeof(int), compare_asc);
    printf("昇順ソート: ");
    for (size_t i = 0; i < arr_size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    // 降順ソート
    qsort(arr, arr_size, sizeof(int), compare_desc);
    printf("降順ソート: ");
    for (size_t i = 0; i < arr_size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

複数のキーによるソート

qsort関数を使って、複数のキーに基づいてソートすることも可能です。

例えば、構造体配列をソートする際に、まず第一キーでソートし、同じ値の場合は第二キーでソートすることができます。

構造体の定義

以下は、学生の名前と成績を持つ構造体の例です。

typedef struct {
    char name[50];
    int score;
} Student;

比較関数の実装

まず、成績でソートし、成績が同じ場合は名前でソートする比較関数を実装します。

int compare_students(const void *a, const void *b) {
    Student *studentA = (Student *)a;
    Student *studentB = (Student *)b;
    if (studentA->score != studentB->score) {
        return studentB->score - studentA->score; // 成績で降順ソート
    } else {
        return strcmp(studentA->name, studentB->name); // 名前で昇順ソート
    }
}

実行例

以下は、学生の構造体配列を成績と名前でソートする例です。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char name[50];
    int score;
} Student;
int compare_students(const void *a, const void *b) {
    Student *studentA = (Student *)a;
    Student *studentB = (Student *)b;
    if (studentA->score != studentB->score) {
        return studentB->score - studentA->score; // 成績で降順ソート
    } else {
        return strcmp(studentA->name, studentB->name); // 名前で昇順ソート
    }
}
int main() {
    Student students[] = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 90},
        {"Dave", 85}
    };
    size_t student_count = sizeof(students) / sizeof(students[0]);
    qsort(students, student_count, sizeof(Student), compare_students);
    printf("ソート後の学生リスト:\n");
    for (size_t i = 0; i < student_count; i++) {
        printf("名前: %s, 成績: %d\n", students[i].name, students[i].score);
    }
    return 0;
}

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

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

例えば、複雑な構造体や他のデータ型を持つ配列をソートすることができます。

カスタムデータ型の定義

以下は、商品名と価格を持つ構造体の例です。

typedef struct {
    char product_name[50];
    double price;
} Product;

比較関数の実装

価格で昇順にソートする比較関数を実装します。

int compare_products(const void *a, const void *b) {
    Product *productA = (Product *)a;
    Product *productB = (Product *)b;
    if (productA->price < productB->price) {
        return -1;
    } else if (productA->price > productB->price) {
        return 1;
    } else {
        return 0;
    }
}

実行例

以下は、商品構造体配列を価格でソートする例です。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char product_name[50];
    double price;
} Product;
int compare_products(const void *a, const void *b) {
    Product *productA = (Product *)a;
    Product *productB = (Product *)b;
    if (productA->price < productB->price) {
        return -1;
    } else if (productA->price > productB->price) {
        return 1;
    } else {
        return 0;
    }
}
int main() {
    Product products[] = {
        {"Laptop", 999.99},
        {"Smartphone", 499.99},
        {"Tablet", 299.99},
        {"Smartwatch", 199.99}
    };
    size_t product_count = sizeof(products) / sizeof(products[0]);
    qsort(products, product_count, sizeof(Product), compare_products);
    printf("ソート後の商品リスト:\n");
    for (size_t i = 0; i < product_count; i++) {
        printf("商品名: %s, 価格: %.2f\n", products[i].product_name, products[i].price);
    }
    return 0;
}

以上のように、qsort関数を使うことで、さまざまなデータ型や条件に基づいて配列をソートすることができます。

比較関数を適切に実装することで、柔軟なソートが可能となります。