アルゴリズム

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

C言語で構造体をクイックソートするには、標準ライブラリのqsort関数を利用します。

構造体の配列をソートする際には、比較関数を定義し、構造体のメンバを基準に比較を行います。

この比較関数はqsortに渡され、ソートの基準として使用されます。

例えば、構造体のメンバである整数や文字列を基準にしてソートを行うことが可能です。

この方法を用いることで、効率的に構造体の配列をソートすることができます。

目次から探す

構造体をクイックソートする方法
応用例
まとめ

構造体をクイックソートする方法

C言語で構造体をクイックソートする方法について解説します。

構造体をソートするためには、比較関数を作成し、標準ライブラリのqsort関数を利用します。

以下にその手順を詳しく説明します。

比較関数の作成

構造体をソートするためには、まず比較関数を作成する必要があります。

この関数は、構造体のメンバーを基準にして2つの構造体を比較し、その結果を返します。

以下は、整数メンバーidを基準に比較する関数の例です。

#include <stdio.h>
typedef struct {
    int id;
    char name[50];
} Person;
// 比較関数
int compareById(const void *a, const void *b) {
    // ポインタをPerson型にキャスト
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    
    // idを基準に比較
    return (personA->id - personB->id);
}

qsort関数の利用

qsort関数は、C言語の標準ライブラリに含まれており、配列をソートするために使用されます。

qsort関数のプロトタイプは以下の通りです。

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

base: ソートする配列の先頭ポインタ
num: 配列の要素数
size: 各要素のサイズ
compar: 比較関数へのポインタ

構造体メンバーによるソート

構造体の特定のメンバーを基準にソートする場合、比較関数をそのメンバーに応じて作成します。

例えば、nameメンバーを基準にソートする場合は、strcmp関数を使用して文字列を比較します。

#include <string.h>
// 名前を基準に比較する関数
int compareByName(const void *a, const void *b) {
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    
    // nameを基準に比較
    return strcmp(personA->name, personB->name);
}

完成したプログラム

以下に、構造体の配列をidでソートする完全なプログラムを示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    int id;
    char name[50];
} Person;
// idを基準に比較する関数
int compareById(const void *a, const void *b) {
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    return (personA->id - personB->id);
}
int main() {
    Person people[] = {
        {3, "Alice"},
        {1, "Bob"},
        {2, "Charlie"}
    };
    int n = sizeof(people) / sizeof(people[0]);
    // qsort関数を使用してソート
    qsort(people, n, sizeof(Person), compareById);
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        printf("ID: %d, Name: %s\n", people[i].id, people[i].name);
    }
    return 0;
}

ID: 1, Name: Bob
ID: 2, Name: Charlie
ID: 3, Name: Alice

このプログラムでは、qsort関数を使用してidを基準に構造体の配列をソートしています。

compareById関数がqsortに渡され、各構造体のidを比較してソートを行います。

結果として、idの昇順に並び替えられた構造体の配列が出力されます。

応用例

構造体のクイックソートは、基本的なソートだけでなく、さまざまな応用が可能です。

ここでは、複数のメンバーを基準にしたソート、構造体のネストを考慮したソート、動的メモリを使用した構造体のソートについて解説します。

複数のメンバーでのソート

複数のメンバーを基準にソートする場合、優先順位を決めて比較関数を作成します。

例えば、idを第一基準、nameを第二基準とする場合の比較関数は以下のようになります。

#include <string.h>
// 複数のメンバーを基準に比較する関数
int compareByIdAndName(const void *a, const void *b) {
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    
    // idを基準に比較
    int idComparison = personA->id - personB->id;
    if (idComparison != 0) {
        return idComparison;
    }
    
    // idが同じ場合、nameを基準に比較
    return strcmp(personA->name, personB->name);
}

この関数では、まずidを比較し、同じ場合はnameを比較します。

これにより、idの昇順、nameの辞書順でソートされます。

構造体のネストとソート

構造体がネストされている場合、ネストされたメンバーを基準にソートすることも可能です。

以下は、ネストされた構造体のメンバーを基準にソートする例です。

typedef struct {
    int year;
    int month;
    int day;
} Date;
typedef struct {
    char name[50];
    Date birthdate;
} Person;
// 生年月日を基準に比較する関数
int compareByBirthdate(const void *a, const void *b) {
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    
    // 年を基準に比較
    if (personA->birthdate.year != personB->birthdate.year) {
        return personA->birthdate.year - personB->birthdate.year;
    }
    // 月を基準に比較
    if (personA->birthdate.month != personB->birthdate.month) {
        return personA->birthdate.month - personB->birthdate.month;
    }
    // 日を基準に比較
    return personA->birthdate.day - personB->birthdate.day;
}

この例では、birthdateというネストされた構造体のメンバーを基準にソートしています。

年、月、日の順に比較を行います。

動的メモリを使った構造体のソート

動的メモリを使用して構造体の配列をソートする場合、mallocやreallocを使用してメモリを確保します。

以下は、動的にメモリを確保して構造体をソートする例です。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    int id;
    char name[50];
} Person;
// idを基準に比較する関数
int compareById(const void *a, const void *b) {
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    return (personA->id - personB->id);
}
int main() {
    int n = 3;
    Person *people = (Person *)malloc(n * sizeof(Person));
    
    // データの入力
    people[0].id = 3; strcpy(people[0].name, "Alice");
    people[1].id = 1; strcpy(people[1].name, "Bob");
    people[2].id = 2; strcpy(people[2].name, "Charlie");
    // qsort関数を使用してソート
    qsort(people, n, sizeof(Person), compareById);
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        printf("ID: %d, Name: %s\n", people[i].id, people[i].name);
    }
    // メモリの解放
    free(people);
    return 0;
}

このプログラムでは、mallocを使用して動的にメモリを確保し、qsortでソートを行っています。

ソート後はfreeを使用してメモリを解放することを忘れないようにしましょう。