マージソート - (void*)Pないと

http://www.geocities.jp/ky_webid/algorithm/021.html

マージソートです。いっぱいありますね、ソートって。

マージソートの最大の特徴は、配列のような直接アクセス（配列であれば添字によるアクセス）ができないリスト構造であっても、ソートを行える点にあります。ただし、他のソートアルゴリズムとは異なり、一時的に大きなメモリ空間を必要とします。

出ました。リスト構造でもソートできるソートのようです。これは完全に覚えないいけないですね。

アルゴリズムの動作例
初期データ: 8 4 3 7 6 5 2 1

データ列を二分割する。

8 4 3 7 | 6 5 2 1

もう一度、二分割する。

8 4 | 3 7 | 6 5 | 2 1

各データ列にデータ数が2以下になったところで、各データ列内のデータをソートする。

4 8 | 3 7 | 5 6 | 1 2

この例の場合は、右2つのデータ列、左2つのデータ列をそれぞれマージとソートし、2つのデータ列にする。

3 4 7 8 | 1 2 5 6

2つのデータ列をマージとソートする。

1 2 3 4 5 6 7 8
マージソート - Wikipedia

なんとなくイメージが付きました。というところで実装してみます。

・・・とかなんとか言いながらいざやってみると全然進みません。もう何が何だかわからないです。マージソート超難い。

仕方なく今回も解答例を軽く読んで自分なりに噛み砕いた上で実装してみたいと思います。

#include <stdio.h>
#include <stdlib.h>
#include "mylib.h"

struct LIST {
    int data;
    struct LIST *next;
};
typedef struct LIST LIST;

LIST *create_list(int data) {
    LIST *p;
    p = (LIST *)malloc(sizeof(LIST));
    if ( p == NULL ) {
        return NULL;
    }
    p->next = NULL;
    p->data = data;
    
    printf("create %p\n",p);
    return p;
}

LIST *add_list (LIST *p,int data) {
    LIST *a = create_list(data);
    
    if ( p->next != NULL ) {
        a->next = p->next;
    }
    p->next = a;
    return a;
}

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

LIST *merge_list (LIST *p1,LIST *p2) {
    LIST out, *p;
    
    p = &out;
    
    while ( p1 != NULL && p2 != NULL ) {
        if ( p1->data <= p2->data ) {
            p->next = p1;
            p = p1;
            p1 = p1->next;
        }
        else {
            p->next = p2;
            p = p2;
            p2 = p2->next;
        }
    }
    
    if ( p1 == NULL ) {
        p->next = p2;
    }
    else {
        p->next = p1;
    }
    
    return out.next;
}

LIST *merge_sort (LIST *p) {
    LIST *a, *b, *y;
    
    if ( p == NULL || p->next == NULL ) return p;
    
    a = p;
    b = p->next->next;
    
    while ( b!=NULL && b->next!=NULL ) {
        a = a->next;
        b = b->next->next;
    }
    
    y = a->next;
    a->next = NULL;
    
    return merge_list( merge_sort(p),merge_sort(y) );
}

int main (void) {
    LIST *head;
    LIST *p;
    int num[] = {7,4,9,0,5,6,7,12,34,78,3,2};
    int i;
    
    p = head = create_list(0);
    for(i=0;i<ARRAY_NUM(num);i++) {
        p = add_list(p,num[i]);
    }
    
    merge_sort(head);
    show_list(head->next);
    
    return 0;
}

できました。一部冗長かな？と思えるところを変えたくらいで殆ど解答例のままですが今回はよしとします。

しかし複雑なアルゴリズムですね、一応理解はできましたが、自分で実装できそうにはないです。