単連結リストの整列 #81 基本選択法での整列関数の実現

整列のアルゴリズムとしてこれまで隣接交換法のみで実装してきたが、他の方法を使ってみよう。
これまでリストの実装の変更などで行っていたのと同様に、
整列関数のインタフェイスはそのままにlistsortの実装を基本選択法に書き換える。

listsort-s.c

#include "listsort.h"

void listsort(
    void *list,
    void *(*head)(const void *, void *),
    void *(*next)(const void *, const void *, void *),
    int (*isvalid)(const void *, const void *, void *),
    void (*swap)(void *, void *, void *, void *),
    void *listarg,
    int (*issup)(const void *, const void *, void *),
    void *arg
) {
    void *p, *q;
    p = head(list, listarg);
    if (! isvalid(list, p, listarg)) return;
    q = next(list, p, listarg);
    while (isvalid(list, q, listarg)) {
        void *s = p;
        do {
            if (issup(s, q, arg)) s = q;
            q = next(list, q, listarg);
        } while (isvalid(list, q, listarg));
        if (p != s) swap(list, p, s, listarg);
        p = next(list, s, listarg);
        q = next(list, p, listarg);
    }
}

隣接交換法よりもシンプルになったような気が。
大雑把には、リストの先頭側に昇順に整列した要素列があり、
その後に未整列の要素列が続いている状態で、
未整列の要素の中で最も順位の低いものを線形探索し、
それと未整列要素列の先頭要素とを交換する。
この要素が整列した要素の中で最高順位の要素であり、
整列した要素列の末尾要素にうまくなっており、未整列の要素は一個減る。
これを繰り返し、未整列の要素が一個になった時点で整列処理は終了する。
残った最後の要素は最も順位の高い要素であり、正しくリストの末尾に位置する。
最初の状態ではリスト全体が未整列であり、
繰り返し処理の一回目では、リスト中、最も順位の低い要素を探して、先頭要素と交換することになる。

コード中、pが未整列要素列の先頭、
qはpの次の要素の参照で初期化した後、未整列要素列を走査するために使う。
その走査が終了した時点でsに最も順位の低い要素の参照が入っている。
sはpで初期化しているので、pがsと異なっていれば両者を交換する。