C言語でプログラミングを学び始めたばかりの方へ、この記事では「線形リスト」を「挿入ソート」という方法で並び替える方法を解説します。
具体的には、ソート関数の呼び出し方、ソート前後のリストの表示方法、そして完全なコード例を紹介します。
線形リストを挿入ソートで並び替える
線形リスト(リンクリスト)は、データ構造の一つで、各要素が次の要素へのポインタを持つことで連結されています。
今回は、この線形リストを挿入ソートアルゴリズムを用いて並び替える方法について解説します。
ソート関数の呼び出し
まず、挿入ソートを実行するための関数を定義し、その関数を呼び出す方法について説明します。
挿入ソートは、リストの各要素を順に取り出し、適切な位置に挿入することでリストを並び替えます。
以下は、挿入ソートを実行する関数 insertionSort のプロトタイプです。
void insertionSort(struct Node** head_ref);この関数は、リストの先頭を指すポインタを引数として受け取り、リストを昇順に並び替えます。
関数の呼び出しは以下のように行います。
insertionSort(&head);ここで、head はリストの先頭を指すポインタです。
ソート前後のリストの表示
ソート前後のリストを表示するためには、リストを順にたどりながら各要素の値を出力する関数を用意します。
以下に、リストを表示する関数 printList の例を示します。
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}この関数を用いて、ソート前後のリストを表示します。
printf("ソート前のリスト:\n");
printList(head);
insertionSort(&head);
printf("ソート後のリスト:\n");
printList(head);完全なコード例
最後に、線形リストを挿入ソートで並び替える完全なコード例を示します。
このコードには、リストのノードを定義する構造体、リストにノードを追加する関数、挿入ソートを実行する関数、およびリストを表示する関数が含まれています。
#include <stdio.h>
#include <stdlib.h>
// ノードの構造体定義
struct Node {
int data;
struct Node* next;
};
// 新しいノードを作成する関数
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// リストの先頭にノードを追加する関数
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = newNode(new_data);
new_node->next = *head_ref;
*head_ref = new_node;
}
// リストを表示する関数
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
// 挿入ソートを実行する関数
void insertionSort(struct Node** head_ref) {
struct Node* sorted = NULL;
struct Node* current = *head_ref;
while (current != NULL) {
struct Node* next = current->next;
if (sorted == NULL || sorted->data >= current->data) {
current->next = sorted;
sorted = current;
} else {
struct Node* temp = sorted;
while (temp->next != NULL && temp->next->data < current->data) {
temp = temp->next;
}
current->next = temp->next;
temp->next = current;
}
current = next;
}
*head_ref = sorted;
}
// メイン関数
int main() {
struct Node* head = NULL;
// リストにノードを追加
push(&head, 5);
push(&head, 20);
push(&head, 4);
push(&head, 3);
push(&head, 30);
printf("ソート前のリスト:\n");
printList(head);
insertionSort(&head);
printf("ソート後のリスト:\n");
printList(head);
return 0;
}このコードを実行すると、以下のような出力が得られます。
ソート前のリスト:
30 -> 3 -> 4 -> 20 -> 5 -> NULL
ソート後のリスト:
3 -> 4 -> 5 -> 20 -> 30 -> NULLこのようにして、線形リストを挿入ソートで並び替えることができます。
挿入ソートは、特にリストがほぼ整列されている場合に効率的なソートアルゴリズムです。
挿入ソートの応用と最適化
挿入ソートは基本的なソートアルゴリズムの一つであり、特に小規模なデータセットやほぼ整列されたデータに対して非常に効率的です。
しかし、データセットが大きくなるとその効率は低下します。
ここでは、挿入ソートの応用例と最適化の方法について解説します。
応用例
部分的に整列されたデータ
挿入ソートは、部分的に整列されたデータに対して非常に効率的です。
例えば、ほとんどの要素が既に整列されている場合、挿入ソートは非常に少ない比較と交換で済みます。
小規模なデータセット
小規模なデータセット(例えば、10個以下の要素)に対しては、挿入ソートは非常に効率的です。
クイックソートやマージソートのような他のアルゴリズムは、オーバーヘッドが大きいため、小規模なデータセットには向いていません。
最適化の方法
バイナリ挿入ソート
通常の挿入ソートでは、挿入位置を見つけるために線形検索を行いますが、バイナリ挿入ソートでは二分探索を用いて挿入位置を見つけます。
これにより、比較回数を減らすことができます。
void binaryInsertionSort(int arr[], int n) {
int i, j, key, left, right, mid;
for (i = 1; i < n; i++) {
key = arr[i];
left = 0;
right = i - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
for (j = i - 1; j >= left; j--)
arr[j + 1] = arr[j];
arr[left] = key;
}
}ギャップ挿入ソート
ギャップ挿入ソートは、シェルソートの一部として使用されることがあります。
これは、要素間のギャップを利用して、より効率的にデータを整列させる方法です。
void gapInsertionSort(int arr[], int n, int gap) {
int i, j, key;
for (i = gap; i < n; i++) {
key = arr[i];
for (j = i; j >= gap && arr[j - gap] > key; j -= gap)
arr[j] = arr[j - gap];
arr[j] = key;
}
}実行結果の例
以下に、バイナリ挿入ソートを用いたソートの実行結果を示します。
#include <stdio.h>
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("ソート前の配列: ");
printArray(arr, n);
binaryInsertionSort(arr, n);
printf("ソート後の配列: ");
printArray(arr, n);
return 0;
}ソート前の配列: 12 11 13 5 6
ソート後の配列: 5 6 11 12 13このように、挿入ソートは特定の条件下で非常に効率的に動作します。
最適化を施すことで、さらにパフォーマンスを向上させることが可能です。
