【C言語】挿入ソートとは？仕組みや実装方法をコード付きで解説

2023年9月10日

目次から探す

挿入ソートの概要

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

挿入ソートは、要素がほぼソートされている場合に効率的なソート方法として知られています。

挿入ソートの目的

挿入ソートの目的は、与えられたデータを昇順または降順に並び替えることです。

挿入ソートは、データの整列が必要な場合や、データの一部をソートする場合に使用されます。

挿入ソートの特徴

挿入ソートの特徴は以下の通りです。

安定なソートアルゴリズムであるため、同じ値を持つ要素の順序が変わらない。
ソート済みの部分列に新しい要素を挿入するため、ソート済みの部分列が大きくなるほど効率が良くなる。
データの移動が発生するため、データの量が多い場合には効率が低下する。

挿入ソートの実装方法

パターン1: 配列を使った実装

以下は、配列を使った挿入ソートの実装例です。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
int main() {
    int arr[] = {5, 2, 8, 12, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("ソート結果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

上記のコードでは、配列を使って挿入ソートを実装しています。

配列の要素を1つずつ取り出し、それを適切な位置に挿入していきます。

パターン2: リストを使った実装

以下は、リストを使った挿入ソートの実装例です。

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
void sortedInsert(struct Node** head_ref, struct Node* new_node) {
    struct Node* current;
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data) {
        new_node->next = *head_ref;
        *head_ref = new_node;
    } else {
        current = *head_ref;
        while (current->next != NULL && current->next->data < new_node->data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}
void insertionSort(struct Node** head_ref) {
    struct Node* sorted = NULL;
    struct Node* current = *head_ref;
    while (current != NULL) {
        struct Node* next = current->next;
        sortedInsert(&sorted, current);
        current = next;
    }
    *head_ref = sorted;
}
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int main() {
    struct Node* head = NULL;
    push(&head, 5);
    push(&head, 2);
    push(&head, 8);
    push(&head, 12);
    push(&head, 1);
    printf("ソート前のリスト: ");
    printList(head);
    insertionSort(&head);
    printf("ソート後のリスト: ");
    printList(head);
    return 0;
}

上記のコードでは、リストを使って挿入ソートを実装しています。

新しい要素を適切な位置に挿入するために、ソート済みのリストを作成していきます。

次のページ挿入ソートの応用例