単連結リストの整列 #6 隣接交換法による実装

本題。
単連結リストを要素の持つ値の昇順に整列する処理を実装する。
せっかくの連結リストなので基本挿入法を使ってもいいが、
とりあえず基本中の基本の隣接交換法を用いてみる。
ここまで積み上げてきているので実装するのは簡単だ。

test_node.c

...snip
static void node_sort(node_t *first_node)
{
    node_t *p, *q;
    if (first_node == NULL || first_node->next == NULL || first_node->next->next == NULL) return;
    for (q = NULL; q != first_node->next->next; q = p->next) {
        for (p = first_node; p->next->next != q; p = p->next) {
            if (p->next->val > p->next->next->val) node_swap(p);
        }
    }
}

int main(void)
{
    size_t i;
    int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    node_t *first_node = node_new(0);
    for (i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
        node_append(first_node, data[i]);
    }
    node_print(first_node);
    node_sort(first_node);
    node_print(first_node);
    return 0;
}

隣接交換法は隣り合う要素を比較して順序が逆なら二つを交換する方法なので、
まさに関数node_swapをそのまま利用できる。

$ ./test_node
9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9

昇順に並べ替えられている。