【C言語】構造体をクイックソートする方法を解説

2023-09-102024-06-03

この記事では、C言語の構造体とクイックソートについて学びます。

構造体は異なるデータ型を一つにまとめる便利な方法で、クイックソートはデータを効率的に並べ替えるアルゴリズムです。

この記事を読むことで、構造体の定義や初期化方法、クイックソートの基本概念と実装方法、そして構造体配列をクイックソートでソートする方法がわかります。

目次から探す

構造体とクイックソートの基本

構造体とは

構造体は、異なるデータ型の変数を一つのまとまりとして扱うことができるデータ構造です。

C言語では、構造体を使うことで、関連するデータを一つの単位として管理することができます。

例えば、学生の情報を管理する場合、名前、年齢、成績などを一つの構造体にまとめることができます。

構造体の定義

構造体はstructキーワードを使って定義します。

以下は、学生の情報を管理する構造体の例です。

struct Student {
    char name[50];
    int age;
    float grade;
};

構造体の宣言と初期化

構造体を定義した後、その構造体を使って変数を宣言し、初期化することができます。

以下は、構造体の宣言と初期化の例です。

struct Student student1 = {"Alice", 20, 3.8};

クイックソートとは

クイックソートは、効率的なソートアルゴリズムの一つで、分割統治法を用いてデータをソートします。

クイックソートは、平均的な時間計算量がO(n log n)であり、非常に高速です。

クイックソートの基本概念

クイックソートは、以下の手順で動作します。

基準値(ピボット)を選択する。
ピボットを基準にデータを分割し、ピボットより小さい要素と大きい要素に分ける。
分割された部分に対して再帰的にクイックソートを適用する。

クイックソートのアルゴリズム概要

クイックソートのアルゴリズムは以下のように実装されます。

配列の要素が1つ以下の場合、ソートは完了。
ピボットを選択し、配列をピボットを基準に分割。
左右の部分配列に対して再帰的にクイックソートを適用。

構造体の定義とデータの準備

構造体の定義方法

構造体を定義するには、structキーワードを使います。

以下は、学生の情報を管理する構造体の定義例です。

struct Student {
    char name[50];
    int age;
    float grade;
};

構造体の宣言

構造体を定義した後、その構造体を使って変数を宣言します。

struct Student student1;

メンバ変数の定義

構造体のメンバ変数は、構造体内で定義される変数です。

上記の例では、name、age、gradeがメンバ変数です。

構造体の配列の作成

構造体の配列を作成することで、複数の構造体を一度に管理することができます。

構造体配列の宣言

構造体の配列を宣言するには、以下のようにします。

struct Student students[3];

構造体配列の初期化

構造体配列を初期化するには、以下のようにします。

struct Student students[3] = {
    {"Alice", 20, 3.8},
    {"Bob", 22, 3.6},
    {"Charlie", 21, 3.9}
};

クイックソートの実装

クイックソート関数の定義

クイックソート関数を定義するには、再帰的な関数を作成します。

クイックソート関数のプロトタイプ宣言

クイックソート関数のプロトタイプ宣言は以下のようにします。

void quicksort(struct Student arr[], int low, int high);

クイックソート関数の実装

クイックソート関数の実装は以下のようになります。

void quicksort(struct Student arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

パーティション関数の実装

パーティション関数は、配列をピボットを基準に分割します。

パーティション関数のプロトタイプ宣言

パーティション関数のプロトタイプ宣言は以下のようにします。

int partition(struct Student arr[], int low, int high);

パーティション関数の実装

パーティション関数の実装は以下のようになります。

int partition(struct Student arr[], int low, int high) {
    struct Student pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j].grade < pivot.grade) {
            i++;
            struct Student temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    struct Student temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

構造体の比較関数の作成

比較関数の必要性

クイックソートを実装する際、構造体の特定のメンバ変数を基準に比較を行う必要があります。

これを実現するために、比較関数を作成します。

比較関数の役割

比較関数は、2つの構造体を比較し、その大小関係を返す役割を持ちます。

比較関数のプロトタイプ宣言

比較関数のプロトタイプ宣言は以下のようにします。

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

比較関数の実装

比較関数の実装は以下のようになります。

int compare(const void *a, const void *b) {
    struct Student *studentA = (struct Student *)a;
    struct Student *studentB = (struct Student *)b;
    return (studentA->grade - studentB->grade);
}

メンバ変数による比較

比較関数では、構造体の特定のメンバ変数を基準に比較を行います。

上記の例では、gradeを基準に比較しています。

比較関数の具体例

以下は、ageを基準に比較する場合の具体例です。

int compareByAge(const void *a, const void *b) {
    struct Student *studentA = (struct Student *)a;
    struct Student *studentB = (struct Student *)b;
    return (studentA->age - studentB->age);
}

クイックソート関数の呼び出し

qsort関数の利用

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

この関数を利用することで、簡単にクイックソートを実装できます。

qsort関数の概要

qsort関数は、配列をソートするための汎用的な関数です。

以下のように宣言されています。

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

qsort関数の引数説明

引数	説明
base	ソートする配列の先頭要素へのポインタ。
nmemb	配列の要素数。
size	各要素のサイズ（バイト単位）。
compar	2つの要素を比較するための関数へのポインタ。この関数は、2つの引数を受け取り、それらの比較結果に基づいて負、0、正の値を返す。

クイックソート関数の呼び出し例

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

qsort(students, 3, sizeof(struct Student), compare);

構造体配列のソート

上記の例では、students配列をgradeを基準にソートしています。

ソート結果の表示

ソート結果を表示するには、以下のようにします。

for (int i = 0; i < 3; i++) {
    printf("Name: %s, Age: %d, Grade: %.2f\n", students[i].name, students[i].age, students[i].grade);
}

実際のコード例

完全なコード例

以下に、構造体の定義からクイックソートの実装、ソート結果の表示までの完全なコード例を示します。

#include <stdio.h>
#include <stdlib.h>
struct Student {
    char name[50];
    int age;
    float grade;
};
int compare(const void *a, const void *b) {
    struct Student *studentA = (struct Student *)a;
    struct Student *studentB = (struct Student *)b;
    return (studentA->grade - studentB->grade);
}
int main() {
    struct Student students[3] = {
        {"Alice", 20, 3.8},
        {"Bob", 22, 3.6},
        {"Charlie", 21, 3.9}
    };
    qsort(students, 3, sizeof(struct Student), compare);
    for (int i = 0; i < 3; i++) {
        printf("Name: %s, Age: %d, Grade: %.2f\n", students[i].name, students[i].age, students[i].grade);
    }
    return 0;
}

構造体の定義

上記のコード例では、struct Studentを定義しています。

この構造体は、name、age、gradeの3つのメンバ変数を持ちます。

クイックソート関数と比較関数の実装

compare関数は、gradeを基準に2つのStudent構造体を比較します。

qsort関数を使って、students配列をソートしています。

メイン関数での呼び出し

main関数では、students配列を初期化し、qsort関数を使ってソートを行い、ソート結果を表示しています。

コードの解説

このコードは、学生の情報を持つ構造体配列を定義し、gradeを基準にソートする例です。

qsort関数を使うことで、簡単にソートを実現しています。

各部分の詳細な説明

要素	説明
struct Student	学生の情報を管理する構造体。
compare	構造体の`grade`を基準に比較する関数。
qsort	標準ライブラリのソート関数。
main	構造体配列の初期化とソート、結果の表示を行う関数。