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

目次から探す

構造体の配列を挿入ソートで並び替える方法

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

挿入ソートは、要素を適切な位置に挿入していくことで配列をソートするアルゴリズムです。

以下では、挿入ソートのアルゴリズムと構造体の配列を挿入ソートする手順について説明します。

挿入ソートのアルゴリズム

挿入ソートのアルゴリズムは以下の手順で行われます。

  1. ソート対象の配列の先頭要素をソート済みとみなします。
  2. 次の要素を取り出し、ソート済みの部分配列の適切な位置に挿入します。
  3. ソート済みの部分配列の要素を右にずらし、挿入する要素の位置を確保します。
  4. 2と3の手順を繰り返し、全ての要素がソート済みの部分配列に挿入されるまで続けます。

構造体の配列を挿入ソートする手順

構造体の配列を挿入ソートする手順は以下の通りです。

  1. ソート対象の構造体の配列を用意します。
  2. 構造体の配列の先頭要素をソート済みとみなします。
  3. 次の要素を取り出し、ソート済みの部分配列の適切な位置に挿入します。

この際、比較する要素は構造体の特定のメンバーとします。

  1. ソート済みの部分配列の要素を右にずらし、挿入する要素の位置を確保します。
  2. 2と3の手順を繰り返し、全ての要素がソート済みの部分配列に挿入されるまで続けます。

以上が、構造体の配列を挿入ソートする手順です。

次に、実際のコード例を示します。

実際のコード例

以下に、構造体の配列を挿入ソートするためのコード例を示します。

#include <stdio.h>
typedef struct {
    int id;
    char name[20];
} Student;
void insertionSort(Student arr[], int n) {
    int i, j;
    Student key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j].id > key.id) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
int main() {
    Student students[] = {
        {3, "Alice"},
        {1, "Bob"},
        {2, "Charlie"},
    };
    int n = sizeof(students) / sizeof(students[0]);
    insertionSort(students, n);
    printf("Sorted students:\n");
    for (int i = 0; i < n; i++) {
        printf("ID: %d, Name: %s\n", students[i].id, students[i].name);
    }
    return 0;
}

上記のコードでは、Studentという構造体を定義し、idnameというメンバーを持っています。

insertionSort関数では、構造体の配列を挿入ソートするためのアルゴリズムが実装されています。

main関数では、実際に構造体の配列を作成し、挿入ソートを行っています。

実行結果は以下のようになります。

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

以上が、構造体の配列を挿入ソートする方法と実際のコード例です。

挿入ソートは比較的シンプルなアルゴリズムですが、効率的なソートアルゴリズムと比べると処理時間が長くなる場合があります。

そのため、大量のデータをソートする場合は他のアルゴリズムを検討することが推奨されます。

目次から探す