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

目次から探す

リスト構造をマージソートする方法

リスト構造をマージソートすることは、データを効率的にソートするための一つの方法です。

マージソートは、分割統治法を用いて実装されており、以下の手順で行われます。

リスト構造のマージソートの手順

  1. リストを半分に分割する

リストの要素数が1以下になるまで、再帰的にリストを分割します。

分割する際には、リストの中央の要素を基準にして分割します。

  1. 分割されたリストをマージする

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

マージする際には、2つのリストの先頭要素を比較し、小さい方を新しいリストに追加します。

リストの要素がなくなるまで、この操作を繰り返します。

  1. ソートされたリストを返す

マージ操作が終了した時点で、ソートされたリストが得られます。

リスト構造のマージソートの実装例

以下に、C言語でリスト構造をマージソートするための実装例を示します。

#include <stdio.h>
#include <stdlib.h>
// リストのノードを表す構造体
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// リストを表示する関数
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
// リストを分割する関数
void splitList(Node* source, Node** front, Node** back) {
    Node* slow = source;
    Node* fast = source->next;
    // fastポインタを2つ進め、slowポインタを1つ進める
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    // slowポインタの次のノードを分割点として設定し、リストを分割する
    *front = source;
    *back = slow->next;
    slow->next = NULL;
}
// 2つのリストをマージする関数
Node* mergeLists(Node* a, Node* b) {
    Node* result = NULL;
    // ベースケース: どちらかのリストが空の場合、もう片方のリストを返す
    if (a == NULL) {
        return b;
    } else if (b == NULL) {
        return a;
    }
    // 2つのリストの先頭要素を比較し、小さい方をresultに追加する
    if (a->data <= b->data) {
        result = a;
        result->next = mergeLists(a->next, b);
    } else {
        result = b;
        result->next = mergeLists(a, b->next);
    }
    return result;
}
// リストをマージソートする関数
void mergeSort(Node** head) {
    Node* current = *head;
    Node* a;
    Node* b;
    // ベースケース: リストが空または要素が1つの場合、ソート済みとみなす
    if (current == NULL || current->next == NULL) {
        return;
    }
    // リストを分割する
    splitList(current, &a, &b);
    // 分割したリストを再帰的にマージソートする
    mergeSort(&a);
    mergeSort(&b);
    // マージしたリストをheadに設定する
    *head = mergeLists(a, b);
}
int main() {
    // サンプルデータのリストを作成する
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));
    Node* fourth = (Node*)malloc(sizeof(Node));
    head->data = 4;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 1;
    third->next = fourth;
    fourth->data = 3;
    fourth->next = NULL;
    printf("ソート前のリスト: ");
    printList(head);
    // リストをマージソートする
    mergeSort(&head);
    printf("ソート後のリスト: ");
    printList(head);
    // メモリの解放
    free(head);
    free(second);
    free(third);
    free(fourth);
    return 0;
}

上記のコードでは、リストを分割する関数splitList、2つのリストをマージする関数mergeLists、リストをマージソートする関数mergeSortが実装されています。

また、main関数では、サンプルデータのリストを作成し、マージソートを実行しています。

実行結果は以下の通りです。

ソート前のリスト: 4 2 1 3 
ソート後のリスト: 1 2 3 4

以上が、リスト構造をマージソートする方法の解説と実装例です。

マージソートは、データのソートに広く利用されるアルゴリズムであり、効率的なソート手法の一つです。

目次から探す