目次から探す
構造体の配列を挿入ソートで並び替える方法
構造体の配列を挿入ソートを使って並び替える方法について解説します。
挿入ソートは、要素を適切な位置に挿入していくことで配列をソートするアルゴリズムです。
以下では、挿入ソートのアルゴリズムと構造体の配列を挿入ソートする手順について説明します。
挿入ソートのアルゴリズム
挿入ソートのアルゴリズムは以下の手順で行われます。
- ソート対象の配列の先頭要素をソート済みとみなします。
- 次の要素を取り出し、ソート済みの部分配列の適切な位置に挿入します。
- ソート済みの部分配列の要素を右にずらし、挿入する要素の位置を確保します。
- 2と3の手順を繰り返し、全ての要素がソート済みの部分配列に挿入されるまで続けます。
構造体の配列を挿入ソートする手順
構造体の配列を挿入ソートする手順は以下の通りです。
- ソート対象の構造体の配列を用意します。
- 構造体の配列の先頭要素をソート済みとみなします。
- 次の要素を取り出し、ソート済みの部分配列の適切な位置に挿入します。
この際、比較する要素は構造体の特定のメンバーとします。
- ソート済みの部分配列の要素を右にずらし、挿入する要素の位置を確保します。
- 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という構造体を定義し、idとnameというメンバーを持っています。
insertionSort関数では、構造体の配列を挿入ソートするためのアルゴリズムが実装されています。
main関数では、実際に構造体の配列を作成し、挿入ソートを行っています。
実行結果は以下のようになります。
Sorted students:
ID: 1, Name: Bob
ID: 2, Name: Charlie
ID: 3, Name: Alice以上が、構造体の配列を挿入ソートする方法と実際のコード例です。
挿入ソートは比較的シンプルなアルゴリズムですが、効率的なソートアルゴリズムと比べると処理時間が長くなる場合があります。
そのため、大量のデータをソートする場合は他のアルゴリズムを検討することが推奨されます。