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

Q: マージソートは他のソートアルゴリズムと比べてどのような利点がありますか？

マージソートは、以下のような利点があります。 安定性 : 同じ値の要素の順序が保持されるため、安定なソートが必要な場合に適しています。 時間計算量 : 最悪の場合でもO(n log n)の時間計算量を持ち、効率的です。 リスト構造への適用 : 配列だけでなく、連結リストにも適用しやすい特性があります。 これらの利点により、特に安定性が求められる場面や、リスト構造を扱う場合に有効な選択肢となります。

連結リストをマージソートする方法は、効率的なソートアルゴリズムの一つです。

マージソートは、リストを再帰的に分割し、各部分をソートしてからマージすることで、全体をソートします。

このアルゴリズムは、分割とマージの過程で新しいリストを作成するため、安定なソートを実現します。

また、連結リストの特性を活かし、配列と異なり追加のメモリをほとんど必要としない点が特徴です。

実装には、リストを半分に分割するための関数と、2つのソート済みリストをマージする関数が必要です。

この記事でわかること

連結リストをマージソートするための手順と実装方法
双方向連結リストや循環連結リストへのマージソートの応用
マージソートの利点と他のソートアルゴリズムとの比較
連結リストのマージソートにおける時間計算量
マージソートを使用する際のメモリ使用量とその考慮点

目次から探す

連結リストをマージソートする手順

必要なデータ構造の定義

連結リストをマージソートするためには、まず基本的なデータ構造を定義する必要があります。

以下に、ノードを表す構造体を定義します。

#include <stdio.h>
#include <stdlib.h>
// ノードを表す構造体
typedef struct Node {
    int data; // データ部分
    struct Node* next; // 次のノードへのポインタ
} Node;

この構造体は、整数データを持つノードと次のノードへのポインタを含んでいます。

分割関数の実装

マージソートでは、リストを半分に分割する必要があります。

以下に、リストを分割する関数を示します。

// リストを2つに分割する関数
void splitList(Node* source, Node** frontRef, Node** backRef) {
    Node* fast;
    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つのソート済みリストをマージする関数
Node* sortedMerge(Node* a, Node* b) {
    Node* result = NULL;
    // ベースケース
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    // aとbのデータを比較して小さい方を選ぶ
    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つのリストを比較しながらマージし、ソートされた新しいリストを返します。

ソート関数の実装

最後に、マージソートを実行するためのメイン関数を実装します。

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

この関数は、リストを再帰的に分割し、ソートされたリストをマージします。

完全なコード例

以下に、連結リストをマージソートする完全なコード例を示します。

#include <stdio.h>
#include <stdlib.h>
// ノードを表す構造体
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 新しいノードを作成する関数
Node* newNode(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
// リストを2つに分割する関数
void splitList(Node* source, Node** frontRef, Node** backRef) {
    Node* fast;
    Node* slow;
    slow = source;
    fast = source->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}
// 2つのソート済みリストをマージする関数
Node* sortedMerge(Node* a, Node* b) {
    Node* result = NULL;
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    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(Node** headRef) {
    Node* head = *headRef;
    Node* a;
    Node* b;
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }
    splitList(head, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *headRef = sortedMerge(a, b);
}
// リストを表示する関数
void printList(Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
// メイン関数
int main() {
    Node* res = NULL;
    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;
}

ソート前のリスト: 
15 10 5 20 3 2 
ソート後のリスト: 
2 3 5 10 15 20

このプログラムは、連結リストをマージソートでソートします。

ソート前とソート後のリストを表示し、正しくソートされていることを確認できます。

応用例

双方向連結リストへの適用

双方向連結リストは、各ノードが次と前のノードへのポインタを持つデータ構造です。

マージソートを双方向連結リストに適用する際には、以下の点に注意が必要です。

データ構造の変更: ノード構造体に前のノードへのポインタを追加します。
マージ関数の修正: マージ時に、前のノードへのポインタも適切に設定する必要があります。

以下に、双方向連結リスト用のノード構造体の例を示します。

// 双方向連結リストのノードを表す構造体
typedef struct DNode {
    int data; // データ部分
    struct DNode* next; // 次のノードへのポインタ
    struct DNode* prev; // 前のノードへのポインタ
} DNode;

双方向連結リストに対するマージソートの実装は、基本的には単方向連結リストと同様ですが、prevポインタの設定を忘れないように注意が必要です。