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

2023-09-102024-08-25

マージソートは、分割統治法を用いた効率的なソートアルゴリズムです。C言語でリスト構造をマージソートするには、まずリストを再帰的に分割し、各部分を個別にソートします。

その後、ソートされた部分をマージして一つのリストに統合します。リストの分割には、通常、リストの中間点を見つける方法が用いられます。

マージの際には、二つのリストの先頭要素を比較し、小さい方を新しいリストに追加する操作を繰り返します。これにより、リスト全体がソートされます。

この記事でわかること

C言語でのリスト構造の基本的な実装方法
リスト構造に対するマージソートの手順と実装例
マージソートの応用例とその利点
マージソートが安定なソートである理由
配列とリストにおけるマージソートの使い分け

目次から探す

C言語でのリスト構造の実装

リスト構造は、データを順序付けて格納するための基本的なデータ構造の一つです。

C言語では、ポインタを用いてリストを実装します。

ここでは、リスト構造の基本的な実装方法について解説します。

ノードの定義

リスト構造を実現するためには、まずノードを定義する必要があります。

ノードはデータと次のノードへのポインタを持つ構造体として定義します。

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

この構造体では、dataがノードに格納されるデータで、nextが次のノードを指すポインタです。

リストの初期化

リストを使用する前に、リストを初期化する必要があります。

初期化では、リストの先頭を指すポインタをNULLに設定します。

// リストの初期化
Node* initializeList() {
    return NULL; // 空のリストを表す
}

この関数は、空のリストを表すNULLポインタを返します。

リストへの要素追加と削除

リストに要素を追加するには、新しいノードを作成し、リストの適切な位置に挿入します。

ここでは、リストの先頭に要素を追加する方法を示します。

// リストの先頭に要素を追加
void addElement(Node** head, int newData) {
    // 新しいノードの作成
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = newData;
    newNode->next = *head; // 現在の先頭を次のノードに設定
    *head = newNode; // 新しいノードを先頭に設定
}

要素を削除するには、削除したい要素を見つけてリストから取り除きます。

ここでは、リストの先頭から要素を削除する方法を示します。

// リストの先頭から要素を削除
void deleteElement(Node** head) {
    if (*head == NULL) return; // リストが空の場合は何もしない
    Node* temp = *head; // 先頭ノードを一時保存
    *head = (*head)->next; // 先頭を次のノードに変更
    free(temp); // メモリを解放
}

これらの関数を用いることで、リストに要素を追加したり削除したりすることができます。

リストの操作は、ポインタを用いることで効率的に行うことができます。

リスト構造をマージソートする手順

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

リスト構造に対しても適用可能で、安定したソートを実現します。

ここでは、リスト構造をマージソートする手順について解説します。

リストを分割する方法

マージソートの最初のステップは、リストを分割することです。

リストを半分に分割するためには、2つのポインタを用いてリストを走査します。

// リストを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;
}

この関数では、slowとfastの2つのポインタを用いてリストを走査し、slowがリストの中央に到達した時点でリストを分割します。

分割したリストをマージする方法

分割したリストをマージするには、2つのリストを比較しながら新しいリストを作成します。

// 2つのリストをマージする関数
Node* mergeLists(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 = mergeLists(a->next, b);
    } else {
        result = b;
        result->next = mergeLists(a, b->next);
    }
    return result;
}

この関数では、aとbのデータを比較し、小さい方のノードを新しいリストに追加していきます。

再帰的にマージソートを適用する

マージソートをリストに適用するには、リストを再帰的に分割し、マージしていきます。

// リストにマージソートを適用する関数
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 = mergeLists(a, b);
}

この関数では、リストを分割し、再帰的にマージソートを適用していきます。

最終的に、ソートされたリストが得られます。

マージソートは、リスト構造においても効率的に動作し、安定したソートを提供します。

C言語でのマージソート実装例

ここでは、リスト構造に対するマージソートの実装例を示します。

各関数の役割と全体の流れを理解することで、効率的なソートアルゴリズムを実装できます。

コード全体の流れ

マージソートの実装は、以下のような流れで行います。

リストを分割する
分割したリストを再帰的にソートする
ソートされたリストをマージする

この流れを実現するために、分割関数、マージ関数、そしてメイン関数を実装します。

分割関数の実装

リストを2つに分割する関数を実装します。

この関数は、リストを前半と後半に分ける役割を持ちます。

// リストを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;
}

この関数では、slowとfastの2つのポインタを用いてリストを走査し、リストを前半と後半に分割します。

マージ関数の実装

分割されたリストをマージする関数を実装します。

この関数は、2つのソート済みリストを1つのソート済みリストに統合します。

// 2つのリストをマージする関数
Node* mergeLists(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 = mergeLists(a->next, b);
    } else {
        result = b;
        result->next = mergeLists(a, b->next);
    }
    return result;
}

この関数では、aとbのデータを比較し、小さい方のノードを新しいリストに追加していきます。

メイン関数での動作確認

最後に、メイン関数でマージソートを実行し、動作を確認します。

int main() {
    Node* res = NULL;
    Node* a = NULL;
    // リストに要素を追加
    addElement(&a, 15);
    addElement(&a, 10);
    addElement(&a, 5);
    addElement(&a, 20);
    addElement(&a, 3);
    addElement(&a, 2);
    // マージソートを適用
    mergeSort(&a);
    // ソート結果を表示
    printf("Sorted Linked List is: \n");
    printList(a);
    return 0;
}

このメイン関数では、リストに要素を追加し、mergeSort関数を呼び出してリストをソートします。

printList関数を用いて、ソートされたリストを表示します。