この記事では、C言語で連結リストをマージソートする方法を解説します。
目次から探す
連結リストのマージソート
連結リストをマージソートする方法について解説します。
マージソートは、分割統治法を用いた効率的なソートアルゴリズムです。
連結リストを使用する場合でも、同様の手法でソートすることができます。
マージソートの手順
マージソートの手順は以下の通りです。
- 連結リストを分割します。
分割する際に、分割する位置を見つけるために分割ポイントを設定します。
- 分割された連結リストを再帰的にマージソートします。
- マージソートされた連結リストをマージします。
マージする際に、マージする位置を見つけるためにマージポイントを設定します。
これらの手順を繰り返すことで、連結リストをソートすることができます。
連結リストの分割
連結リストを分割するためには、分割ポイントを設定する必要があります。
分割ポイントは、連結リストの中央に位置するノードを選ぶことが一般的です。
連結リストの中央を見つけるために、2つのポインタを使用します。
1つのポインタは1つずつ進み、もう1つのポインタは2つずつ進みます。
2つずつ進むポインタが終端に達した時点で、1つずつ進むポインタが指す位置が分割ポイントとなります。
連結リストのマージ
マージソートされた2つの連結リストをマージするためには、マージポイントを設定する必要があります。
マージポイントは、2つの連結リストの先頭ノードを比較し、小さい方を新しい連結リストに追加することで求めることができます。
その後、小さい方のノードを次のノードに進め、再び比較を行います。
この操作を繰り返すことで、2つの連結リストをマージすることができます。
マージソートの実装例
以下に、連結リストをマージソートするための実装例を示します。
マージソートの関数定義
// ノードの構造体
typedef struct Node {
int data;
struct Node* next;
} Node;
// マージソートの関数
Node* mergeSort(Node* head);連結リストの分割関数の実装
// 連結リストを分割する関数
Node* splitList(Node* head) {
Node* slow = head;
Node* fast = head;
Node* prev = NULL;
while (fast != NULL && fast->next != NULL) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
return slow;
}連結リストのマージ関数の実装
// 連結リストをマージする関数
Node* mergeLists(Node* list1, Node* list2) {
if (list1 == NULL) {
return list2;
}
if (list2 == NULL) {
return list1;
}
Node* result = NULL;
if (list1->data <= list2->data) {
result = list1;
result->next = mergeLists(list1->next, list2);
} else {
result = list2;
result->next = mergeLists(list1, list2->next);
}
return result;
}以上が、連結リストをマージソートするための実装例です。
これらの関数を組み合わせて、連結リストをマージソートすることができます。