【C言語】連結リストをマージソートする方法を解説

2023-09-102024-06-03

この記事では、C言語を使って連結リストをマージソートする方法を学びます。

マージソートは、リストを2つに分割し、それぞれをソートしてから再び1つにマージするアルゴリズムです。

具体的な手順やコード例を通じて、初心者でも理解しやすいように解説します。

目次から探す

マージソートの実装手順

マージソートは、分割統治法を用いた効率的なソートアルゴリズムです。

連結リストに対しても適用可能で、リストを再帰的に分割し、マージしてソートします。

以下では、連結リストをマージソートする手順を詳しく解説します。

リストの分割

リストを2つに分割する方法

連結リストを2つに分割するためには、リストの中央を見つける必要があります。

これには、2つのポインタを使う方法が一般的です。

1つのポインタは1ステップずつ進み、もう1つのポインタは2ステップずつ進みます。

2ステップ進むポインタがリストの終端に達したとき、1ステップ進むポインタはリストの中央に位置します。

分割のための関数の実装

以下に、連結リストを2つに分割する関数の実装例を示します。

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
struct Node {
    int data;
    struct Node* next;
};
// リストを2つに分割する関数
void splitList(struct Node* source, struct Node** frontRef, struct Node** backRef) {
    struct Node* fast;
    struct Node* slow;
    slow = source;
    fast = source->next;
    // fastがリストの終端に達するまで進む
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    // slowはリストの中央に位置する
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

マージ操作

2つのリストをマージする方法

2つのソート済みリストを1つのソート済みリストにマージするには、各リストの先頭から順に比較し、小さい方の要素を新しいリストに追加していきます。

マージのための関数の実装

以下に、2つのソート済みリストをマージする関数の実装例を示します。

// 2つのソート済みリストをマージする関数
struct Node* sortedMerge(struct Node* a, struct Node* b) {
    struct Node* result = NULL;
    // ベースケース
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    // aとbのデータを比較し、小さい方をresultに追加
    if (a->data <= b->data) {
        result = a;
        result->next = sortedMerge(a->next, b);
    } else {
        result = b;
        result->next = sortedMerge(a, b->next);
    }
    return result;
}

再帰的なソート

再帰的にリストをソートする方法

リストを再帰的にソートするためには、まずリストを2つに分割し、それぞれを再帰的にソートします。

その後、2つのソート済みリストをマージします。

ソートのための関数の実装

以下に、連結リストを再帰的にソートする関数の実装例を示します。

// マージソートを実行する関数
void mergeSort(struct Node** headRef) {
    struct Node* head = *headRef;
    struct Node* a;
    struct Node* b;
    // ベースケース: リストが空または1つの要素しかない場合
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }
    // リストを2つに分割
    splitList(head, &a, &b);
    // それぞれのリストを再帰的にソート
    mergeSort(&a);
    mergeSort(&b);
    // 2つのソート済みリストをマージ
    *headRef = sortedMerge(a, b);
}

完成したコード

以上の関数を組み合わせて、連結リストをマージソートする完全なコードを以下に示します。

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
struct Node {
    int data;
    struct Node* next;
};
// リストを2つに分割する関数
void splitList(struct Node* source, struct Node** frontRef, struct Node** backRef) {
    struct Node* fast;
    struct Node* slow;
    slow = source;
    fast = source->next;
    // fastがリストの終端に達するまで進む
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    // slowはリストの中央に位置する
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}
// 2つのソート済みリストをマージする関数
struct Node* sortedMerge(struct Node* a, struct Node* b) {
    struct Node* result = NULL;
    // ベースケース
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    // aとbのデータを比較し、小さい方をresultに追加
    if (a->data <= b->data) {
        result = a;
        result->next = sortedMerge(a->next, b);
    } else {
        result = b;
        result->next = sortedMerge(a, b->next);
    }
    return result;
}
// マージソートを実行する関数
void mergeSort(struct Node** headRef) {
    struct Node* head = *headRef;
    struct Node* a;
    struct Node* b;
    // ベースケース: リストが空または1つの要素しかない場合
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }
    // リストを2つに分割
    splitList(head, &a, &b);
    // それぞれのリストを再帰的にソート
    mergeSort(&a);
    mergeSort(&b);
    // 2つのソート済みリストをマージ
    *headRef = sortedMerge(a, b);
}
// 新しいノードを作成する関数
struct Node* newNode(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
// リストを表示する関数
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
// メイン関数
int main() {
    struct Node* res = NULL;
    struct Node* a = NULL;
    // リストにデータを追加
    a = newNode(15);
    a->next = newNode(10);
    a->next->next = newNode(5);
    a->next->next->next = newNode(20);
    a->next->next->next->next = newNode(3);
    a->next->next->next->next->next = newNode(2);
    // ソート前のリストを表示
    printf("ソート前のリスト: \n");
    printList(a);
    // マージソートを実行
    mergeSort(&a);
    // ソート後のリストを表示
    printf("ソート後のリスト: \n");
    printList(a);
    return 0;
}

このコードを実行すると、連結リストがマージソートによってソートされる様子が確認できます。

ソート前とソート後のリストが表示されるので、正しく動作していることがわかります。