【C言語】構造体を挿入ソートで並び替える方法を解説

2023-09-102024-06-03

この記事では、C言語で構造体を使ってデータを管理し、挿入ソートというアルゴリズムを使って並び替える方法を解説します。

具体的には、比較関数の作成方法、挿入ソートの実装方法、そしてソート結果の確認方法について学びます。

また、応用例として複数のキーでのソートや動的メモリを使ったソート、ネストされた構造体のソートについても紹介します。

目次から探す

構造体を挿入ソートで並び替える手順

C言語で構造体を挿入ソートを用いて並び替える方法について解説します。

構造体をソートするためには、まず比較関数を作成し、その後に挿入ソートのアルゴリズムを実装します。

最後に、ソートを実行して結果を確認します。

比較関数の作成

比較関数の基本

比較関数は、2つの要素を比較してその大小関係を返す関数です。

C言語では、通常、比較関数は以下のような形式で定義されます。

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

この関数は、2つのポインタを引数として受け取り、それらが指す要素を比較します。

返り値は以下のようになります。

a < b の場合：負の値
a == b の場合：0
a > b の場合：正の値

比較基準の設定

次に、構造体のどのメンバを基準に比較するかを決めます。

例えば、以下のような構造体 Person があるとします。

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

この場合、年齢 (age) を基準に比較する関数を作成します。

int compareByAge(const void *a, const void *b) {
    Person *personA = (Person *)a;
    Person *personB = (Person *)b;
    return personA->age - personB->age;
}

挿入ソートの実装

挿入ソートの基本構造

挿入ソートは、配列を部分的にソートしながら進めるアルゴリズムです。

以下は、基本的な挿入ソートの実装です。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

構造体の配列に対する挿入ソートの適用

次に、構造体の配列に対して挿入ソートを適用します。

以下のコードは、構造体 Person の配列を年齢順にソートする挿入ソートの実装です。

void insertionSort(Person arr[], int n, int (*compare)(const void *, const void *)) {
    for (int i = 1; i < n; i++) {
        Person key = arr[i];
        int j = i - 1;
        while (j >= 0 && compare(&arr[j], &key) > 0) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

ソートの実行と結果の確認

ソート関数の呼び出し

次に、ソート関数を呼び出して実行します。

以下のコードは、構造体 Person の配列を作成し、挿入ソートを実行する例です。

int main() {
    Person people[] = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };
    int n = sizeof(people) / sizeof(people[0]);
    insertionSort(people, n, compareByAge);
    // ソート結果の出力
    for (int i = 0; i < n; i++) {
        printf("Name: %s, Age: %d\n", people[i].name, people[i].age);
    }
    return 0;
}

ソート結果の出力

上記のコードを実行すると、以下のようにソートされた結果が出力されます。

Name: Bob, Age: 25
Name: Alice, Age: 30
Name: Charlie, Age: 35

このようにして、構造体の配列を挿入ソートで並び替えることができます。

比較関数を適切に作成し、挿入ソートのアルゴリズムを実装することで、任意の基準で構造体をソートすることが可能です。

応用例

複数のキーでのソート

構造体をソートする際、単一のキーだけでなく複数のキーを使ってソートすることも可能です。

例えば、学生の成績データを「名前」と「点数」の両方でソートする場合を考えてみましょう。

まずは点数でソートし、点数が同じ場合は名前でソートするという方法です。

以下に、複数のキーでソートするための比較関数の例を示します。

#include <stdio.h>
#include <string.h>
typedef struct {
    char name[50];
    int score;
} Student;
int compare(const void *a, const void *b) {
    Student *studentA = (Student *)a;
    Student *studentB = (Student *)b;
    // 点数で比較
    if (studentA->score != studentB->score) {
        return studentB->score - studentA->score; // 降順
    }
    // 点数が同じ場合は名前で比較
    return strcmp(studentA->name, studentB->name);
}
int main() {
    Student students[] = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 90},
        {"Dave", 85}
    };
    int n = sizeof(students) / sizeof(students[0]);
    qsort(students, n, sizeof(Student), compare);
    for (int i = 0; i < n; i++) {
        printf("%s: %d\n", students[i].name, students[i].score);
    }
    return 0;
}

このコードでは、まず点数で比較し、点数が同じ場合は名前で比較するようにしています。

qsort関数を使ってソートを行い、結果を出力しています。

動的メモリを使用した構造体配列のソート

動的メモリを使用して構造体配列をソートする場合、mallocやfreeを使ってメモリを動的に確保および解放します。

以下にその例を示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char name[50];
    int score;
} Student;
int compare(const void *a, const void *b) {
    Student *studentA = (Student *)a;
    Student *studentB = (Student *)b;
    return studentB->score - studentA->score; // 降順
}
int main() {
    int n;
    printf("学生の数を入力してください: ");
    scanf("%d", &n);
    Student *students = (Student *)malloc(n * sizeof(Student));
    if (students == NULL) {
        printf("メモリの確保に失敗しました\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        printf("学生 %d の名前と点数を入力してください: ", i + 1);
        scanf("%s %d", students[i].name, &students[i].score);
    }
    qsort(students, n, sizeof(Student), compare);
    printf("ソート後の学生リスト:\n");
    for (int i = 0; i < n; i++) {
        printf("%s: %d\n", students[i].name, students[i].score);
    }
    free(students);
    return 0;
}

このコードでは、ユーザーから学生の数を入力させ、その数に応じて動的にメモリを確保しています。

qsort関数を使ってソートを行い、結果を出力した後、free関数でメモリを解放しています。

構造体のネストとソート

構造体の中に別の構造体を含む「ネストされた構造体」をソートすることも可能です。

例えば、学生の情報に加えて、住所情報を持つ構造体を考えてみましょう。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char city[50];
    char street[50];
} Address;
typedef struct {
    char name[50];
    int score;
    Address address;
} Student;
int compare(const void *a, const void *b) {
    Student *studentA = (Student *)a;
    Student *studentB = (Student *)b;
    return studentB->score - studentA->score; // 降順
}
int main() {
    Student students[] = {
        {"Alice", 90, {"Tokyo", "Shibuya"}},
        {"Bob", 85, {"Osaka", "Namba"}},
        {"Charlie", 90, {"Tokyo", "Shinjuku"}},
        {"Dave", 85, {"Kyoto", "Gion"}}
    };
    int n = sizeof(students) / sizeof(students[0]);
    qsort(students, n, sizeof(Student), compare);
    for (int i = 0; i < n; i++) {
        printf("%s: %d, %s, %s\n", students[i].name, students[i].score, students[i].address.city, students[i].address.street);
    }
    return 0;
}

このコードでは、Addressという構造体を定義し、それをStudent構造体のメンバーとして使用しています。

ソートの基準は点数で、qsort関数を使ってソートを行い、結果を出力しています。

これらの応用例を通じて、構造体を使ったデータの管理とソートの方法をさらに深く理解できるでしょう。

複数のキーでのソートや動的メモリの使用、ネストされた構造体のソートなど、実際のプログラムで役立つテクニックを学ぶことができます。