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

C言語で構造体を挿入ソートで並び替える方法について解説します。構造体は複数のデータ型をまとめて扱うことができるため、特定のメンバを基準にソートすることが可能です。

挿入ソートは、データを順次比較しながら適切な位置に挿入していくシンプルなアルゴリズムです。構造体の配列をソートする際には、比較対象となるメンバを指定し、forループやif文を用いて要素を入れ替えます。

この方法を用いることで、特定の条件に基づいて構造体の配列を効率的に並び替えることができます。

この記事でわかること

構造体を挿入ソートで並び替える手順
比較関数の作成方法
構造体のメンバーによるソートの応用例
複数のキーでのソート方法
挿入ソートの利点とパフォーマンス改善策

目次から探す

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

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

挿入ソートは、データを順次並べ替えるシンプルなアルゴリズムで、特に小規模なデータセットに適しています。

以下の手順で、構造体を挿入ソートで並び替える方法を学びましょう。

ソート対象の構造体の選定

まず、ソート対象となる構造体を定義します。

ここでは、例として学生の情報を持つ構造体を使用します。

#include <stdio.h>
#include <string.h>
// 学生情報を表す構造体
typedef struct {
    char name[50];  // 名前
    int score;      // 点数
} Student;

この構造体は、学生の名前と点数を格納します。

ソートの基準として、点数を使用します。

比較関数の作成

次に、構造体のメンバーを比較するための関数を作成します。

この関数は、2つの構造体を受け取り、比較結果を返します。

// 2つの学生の点数を比較する関数
int compareStudents(const Student *a, const Student *b) {
    return a->score - b->score;
}

この関数は、aの点数がbより大きければ正の値、小さければ負の値、等しければ0を返します。

挿入ソートの実装

挿入ソートを実装し、構造体の配列を並び替えます。

構造体配列のソート

以下のコードは、挿入ソートを用いて構造体の配列を並び替える実装です。

// 構造体配列を挿入ソートで並び替える関数
void insertionSort(Student arr[], int n) {
    for (int i = 1; i < n; i++) {
        Student key = arr[i];
        int j = i - 1;
        // 点数がkeyより大きい間、後ろにシフト
        while (j >= 0 && compareStudents(&arr[j], &key) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

この関数は、配列arrを受け取り、挿入ソートを適用して並び替えます。

ソートの実行と確認

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

int main() {
    Student students[] = {
        {"Alice", 85},
        {"Bob", 95},
        {"Charlie", 75}
    };
    int n = sizeof(students) / sizeof(students[0]);
    insertionSort(students, n);
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        printf("名前: %s, 点数: %d\n", students[i].name, students[i].score);
    }
    return 0;
}

名前: Charlie, 点数: 75
名前: Alice, 点数: 85
名前: Bob, 点数: 95

このプログラムは、学生の点数に基づいて構造体の配列を昇順に並び替えます。

挿入ソートを用いることで、シンプルかつ効率的に小規模なデータセットをソートできます。

完成したプログラム

ここでは、これまでに解説した内容を基に、構造体を挿入ソートで並び替える完成したプログラムを紹介します。

このプログラムは、学生の名前と点数を持つ構造体の配列を、点数に基づいて昇順に並び替えます。

#include <stdio.h>
#include <string.h>
// 学生情報を表す構造体
typedef struct {
    char name[50];  // 名前
    int score;      // 点数
} Student;
// 2つの学生の点数を比較する関数
int compareStudents(const Student *a, const Student *b) {
    return a->score - b->score;
}
// 構造体配列を挿入ソートで並び替える関数
void insertionSort(Student arr[], int n) {
    for (int i = 1; i < n; i++) {
        Student key = arr[i];
        int j = i - 1;
        // 点数がkeyより大きい間、後ろにシフト
        while (j >= 0 && compareStudents(&arr[j], &key) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
int main() {
    Student students[] = {
        {"Alice", 85},
        {"Bob", 95},
        {"Charlie", 75}
    };
    int n = sizeof(students) / sizeof(students[0]);
    insertionSort(students, n);
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        printf("名前: %s, 点数: %d\n", students[i].name, students[i].score);
    }
    return 0;
}

名前: Charlie, 点数: 75
名前: Alice, 点数: 85
名前: Bob, 点数: 95

このプログラムは、insertionSort関数を使用して、学生の点数に基づいて構造体の配列を並び替えます。

compareStudents関数は、2つの構造体の点数を比較し、挿入ソートの基準として使用されます。

main関数では、ソートされた結果を表示し、正しく並び替えられたことを確認できます。

応用例

挿入ソートを用いた構造体の並び替えは、さまざまな応用が可能です。

ここでは、構造体のメンバーによるソート、複数のキーでのソート、動的メモリを使用した構造体のソートについて解説します。

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

構造体の異なるメンバーを基準にソートすることも可能です。

例えば、学生の名前でソートする場合、比較関数を以下のように変更します。

// 2つの学生の名前を比較する関数
int compareStudentsByName(const Student *a, const Student *b) {
    return strcmp(a->name, b->name);
}

この関数を使用して、insertionSort関数内で名前を基準にソートすることができます。

複数のキーでのソート

複数のキーでソートする場合、まず第一のキーでソートし、同じ値の場合は第二のキーでソートします。

例えば、点数でソートし、同点の場合は名前でソートする場合、以下のように比較関数を作成します。

// 点数で比較し、同点の場合は名前で比較する関数
int compareStudentsByScoreAndName(const Student *a, const Student *b) {
    int scoreComparison = a->score - b->score;
    if (scoreComparison != 0) {
        return scoreComparison;
    }
    return strcmp(a->name, b->name);
}

この関数を用いることで、複数のキーに基づいたソートが可能になります。

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

動的メモリを使用して構造体をソートする場合、mallocやfreeを用いてメモリを管理します。

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

#include <stdlib.h>
// 動的メモリを使用して構造体配列を作成し、ソートする関数
void sortStudentsDynamically() {
    int n = 3;
    Student *students = (Student *)malloc(n * sizeof(Student));
    // 学生情報を動的に設定
    strcpy(students[0].name, "Alice");
    students[0].score = 85;
    strcpy(students[1].name, "Bob");
    students[1].score = 95;
    strcpy(students[2].name, "Charlie");
    students[2].score = 75;
    // ソート
    insertionSort(students, n);
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        printf("名前: %s, 点数: %d\n", students[i].name, students[i].score);
    }
    // メモリを解放
    free(students);
}

この例では、mallocを使用して構造体の配列を動的に確保し、freeで解放しています。

動的メモリを使用することで、実行時に必要なメモリ量を柔軟に管理できます。