C言語教室 第27回 いろいろなソート(続)

前回はバブルソートについて説明しましたが、今回はマージソートを取り上げます。マージソートとは、整列してある複数のデータ列をにひとつのデータ列するまとめる際に、小さいものから先に新しい列にデータ並べれば、新しいデータ列も整列されているということで、データ列を分割し、それぞれのデータ列に含まれる値をマージソートしていくことで、全体をソートします。

マージソート

マージソート - Wikipedia

元々はメモリに収まらないような大きなデータをソートするために考えられたようです。ディスク（当時はテープでしょうね）から読み出してソートするのに向いているアルゴリズムです。そうそう、あのフォン・ノイマン氏が考案したらしいです。普通はソートのための作業領域がデータの分だけ必要になるのですが、よく使われるクイックソートと比べても遜色のない速度が出ます。

今回は、このマージソートのアルゴリズムを使って、配列ではなくてリスト構造に格納されているデータをソートしてみます。リストをソートする場合は、作業領域を使わずにポインタを付け替えていくだけでソートできるのです。早速コードを見てみましょう。

#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君は、何かを表示しかけたのに、そのまま諦めちゃうし

すみません、違う話題にしましょう。ほかにどんなことを考えていますか？

BingAI

Bard君は、実行しても何もしないコードを吐いてくるし

そんなに難しいことをしているつもりは無いのだけど、世の中にあまりC言語で書かれたマージソートのコードがないのだろうか。

ヘッダ画像は、Bing Image Creator で作成しました。

#C言語 #プログラミング講座 #ソート #マージソート #リスト #生成AI