C言語教室 第27回 いろいろなソート(続)
前回はバブルソートについて説明しましたが、今回はマージソートを取り上げます。マージソートとは、整列してある複数のデータ列をにひとつのデータ列するまとめる際に、小さいものから先に新しい列にデータ並べれば、新しいデータ列も整列されているということで、データ列を分割し、それぞれのデータ列に含まれる値をマージソートしていくことで、全体をソートします。
マージソート
元々はメモリに収まらないような大きなデータをソートするために考えられたようです。ディスク（当時はテープでしょうね）から読み出してソートするのに向いているアルゴリズムです。そうそう、あのフォン・ノイマン氏が考案したらしいです。普通はソートのための作業領域がデータの分だけ必要になるのですが、よく使われるクイックソートと比べても遜色のない速度が出ます。
今回は、このマージソートのアルゴリズムを使って、配列ではなくてリスト構造に格納されているデータをソートしてみます。リストをソートする場合は、作業領域を使わずにポインタを付け替えていくだけでソートできるのです。早速コードを見てみましょう。
#include <stdio.h>
#include <stdlib.h>
/* ノードの構造体 */
typedef struct node {
int data;
struct node* next;
} Node;
/* 連結リストの表示 */
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
/* 連結リストを分割する */
void splitList(Node* source, Node** frontRef, Node** backRef) {
Node* slow;
Node* fast;
/* 分割位置を見つける */
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
/* slowを分割位置として設定 */
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
/* 連結リストをマージする */
Node* merge(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 = merge(a->next, b);
} else {
result = b;
result->next = merge(a, b->next);
}
return result;
}
/* 連結リストをマージソートする */
void mergeSort(Node** headRef) {
Node* head = *headRef;
Node* a;
Node* b;
/* ベースケース：リストが空または1つの要素しかない場合 */
if (head == NULL || head->next == NULL)
return;
/* 連結リストを分割する */
splitList(head, &a, &b);
/* 分割したリストを再帰的にマージソートする */
mergeSort(&a);
mergeSort(&b);
/* マージしてソートしたリストを再接続する */
*headRef = merge(a, b);
}
/* 連結リストに要素を追加する */
void push(Node** headRef, int newData) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newData;
newNode->next = (*headRef);
(*headRef) = newNode;
}
void main() {
Node* head = NULL;
/* テスト用のデータを追加 */
push(&head, 9);
push(&head, 5);
push(&head, 9);
push(&head, 2);
push(&head, 7);
push(&head, 3);
printf("Origin:");
printList(head);
/* 連結リストをマージソートする */
mergeSort(&head);
printf("Result:");
printList(head);
}このコードを実行すると
Origin:3 7 2 9 5 9
Result:2 3 5 7 9 9 と出力されます。どうやら並べ替えることが出来たようですね。リストを検索する時にソートされていると楽なことが多いので、ぜひ覚えておきましょう。
課題
1. 整数と文字列を持つ構造体のリストを用意して、整数での並べかえと文字列での並べかえを、それぞれ昇順でマージソートする関数を書きなさい。
2. 文字列（ポインタの）配列をマージソートする関数を書きなさい。
再帰を用いないリストのマージソートも見てみたいのですが、ちょっと大変そうです。解答は用意しないので、興味のある方は自由課題として挑戦してみてください。
余談
Bing君は、何かを表示しかけたのに、そのまま諦めちゃうし
すみません、違う話題にしましょう。ほかにどんなことを考えていますか？
Bard君は、実行しても何もしないコードを吐いてくるし
そんなに難しいことをしているつもりは無いのだけど、世の中にあまりC言語で書かれたマージソートのコードがないのだろうか。
ヘッダ画像は、Bing Image Creator で作成しました。