ももの知恵の樹

C言語アルゴリズム-マージソート

マージソート(merge sort)

マージソートとは、データ列の中心で2つの部分列に分割し、それぞれで整列を行った後、整列済み部分列を併合（マージ）する整列アルゴリズムです。あらかじめ整列してある2つのデータ列を合体させて、新しい整列されたデータ列を得ることは容易であることに着目した整列法です。


マージソートのどのような場合でも計算量が「O(N Log N)」となり、クイックソートよりも最悪計算量が少なくなります。特に、リスト構造の整列としては、クイックソートより効率が良いといえます。


マージソートの整列過程

基本的なソート処理の流れは以下の通りです。

  1. データ列を（等分に）分割する。
  2. 各データ列のデータ数が2以下になったところで、各データ列内のデータをソートする。
  3. ソートされたデータ列をマージする。 

[before]   : 8 6 1 4 2 3 7 5
[partition]:(8 6 1 4) (2 3 7 5)
[partition]:(8 6) (1 4) (2 3) (7 5)
[merge]    :(6 8) (1 4) (2 3) (5 7)
[merge]    :(1 4 6 8) (2 3 5 7)
[merge]    :(1 2 3 4 5 6 7 8)
[after]    : 1 2 3 4 5 6 7 8

C言語によるリスト構造データをマージソートするプログラム


#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <time.h>

/* セルの定義 */
struct cell{
    struct cell *next;
    int data;
};
typedef struct cell cell_t;

/*!
 * @brief       新規セルを生成する。
 * @param[in]   data  データ
 * @return      新規セルのアドレスを返す。失敗の場合はNULLを返す。
 */
cell_t *
list_alloc(int data)
{
    cell_t *new = NULL;

    new = (cell_t *)malloc(sizeof(cell_t));
    if(new == NULL){
        fprintf(stderr, "ERROR: list_alloc(): %s\n", strerror(errno));
        return(NULL);
    }

    new->next = NULL;
    new->data = data;

    return(new);
}

/*!
 * @brief      リスト末尾に新規セルを追加する
 * @param[in]  header  リストの先頭要素
 * @param[in]  data  データ
 */
int
list_add(cell_t *header, int data)
{
    cell_t *next = NULL;
    cell_t *prev = header;

    /* セルを生成する */
    next = list_alloc(data);
    if(next == NULL) return(-1);

    /* 末尾にセルを追加する */
    while(prev->next != NULL){
        prev = prev->next;
    }
    prev->next = next;

    return(0);
}

/*!
 * @brief      リストの要素を全て解放する
 * @param[in]  header  リストの先頭要素
 */
void
list_free(cell_t *header)
{
    cell_t *temp = header;
    cell_t *swap = NULL;

    while(temp != NULL){
        swap = temp->next;
        free(temp);
        temp = swap;
    }
}

/*!
 * @brief      リストの要素を一覧表示する
 * @param[in]  header  リストの先頭要素
 */
static void
list_print(cell_t *header)
{
    cell_t *p = header;

    printf("list{ ");
    while(p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("}\n");
}

/*!
 * @brief      リストをマージする
 * @param[in]  list1  連結リスト
 * @param[in]  list2  連結リスト
 * @return     マージ済みリストの先頭アドレスを返す
 */
static cell_t *
merge_list(cell_t *list1, cell_t *list2)
{
    cell_t dummy = {0};
    cell_t *p = NULL;
    p = &dummy;

    while((list1 != NULL) && (list2 != NULL)){
        /* 先頭要素を比較する */
        if(list1->data <= list2->data){
            p->next = list1;     /* マージ済みリストの末尾に連結する */
            p = list1;
            list1 = list1->next; /* リストの次の要素をセットする */
        }else{
            p->next = list2;
            p = list2;
            list2 = list2->next;
        }
    }

    /* 残りの要素をマージ済みリストの末尾に連結する */
    if(list1 == NULL){
        p->next = list2;
    }else{
        p->next = list1;
    }
    return(dummy.next);
}

/*!
 * @brief      マージソートを行う
 * @param[in]  header  リストの先頭要素
 * @return     整列済みリストの先頭アドレスを返す
 */
cell_t *
merge_sort(cell_t *header)
{
    cell_t *partition = NULL;         /* 分割位置 */
    cell_t *forward   = header;       /* 分割時の前位置 */
    cell_t *backward  = header->next; /* 分割時の後位置 */

    /* 要素が１以下の場合は分割しない */
    if((header == NULL) || (header->next == NULL)) return(header);

    /* 分割位置の決定（１：２でポインタを進める） */
    if(backward != NULL) backward = backward->next;
    while((backward != NULL) && (backward->next != NULL)){
        forward = forward->next;
        backward = backward->next->next;
    }

    /* リストを切断する */
    partition = forward->next;
    forward->next = NULL;

    /* 分割を繰り返してからマージする */
    return(merge_list(merge_sort(header), merge_sort(partition)));
}

int
main(void)
{
    int cnt = 0;

    /* 先頭セルを用意する */
    cell_t *header = list_alloc(0); /* 0をダミーデータとする */
    if(header == NULL) return(-1);

    /* リストに要素を追加する */
    srand((unsigned int)time(NULL)); /* 起動毎に異なる乱数を発生させる */
    for(cnt = 0; cnt < 30; cnt++){
        list_add(header, rand());
    }

    /* 整列する */
    printf("[before]:"); list_print(header);
    header = merge_sort(header);
    printf("[after] :"); list_print(header);

    /* リストを解放する */
    list_free(header);

    return(0);
}

関連ページ