単連結リストの整列 #68 良くて要素数の二次オーダの時間計算量になる整列処理も意図に無い比較を無くす

一通りの走査で隣接要素の交換が一度も行われなかった場合に整列処理を打ち切るという変更を行ったわけだが、
ついでなので、順序が逆だが、この変更前のものについても前回行ったように無用な比較を行わないように変える。
これまで述べたようにそうしなくても誤った結果になるわけではなく無用な処理が行われるだけではある。
ただ、一走査零交換でも最後まで整列処理をするというような既知の無用処理とは異なり、
設計意図の範囲外にある思っていなかった無用な処理というものはバグ的であり無くすべきものだろう。

listsort.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, *r, *s;
    q = head(list, listarg);
    if (! isvalid(list, q, listarg)) return;
    r = next(list, q, listarg);
    if (! isvalid(list, r, listarg)) return;
    for (;;) {
        if (issup(q, r, arg)) {
            swap(list, q, r, listarg);
            s = next(list, q, listarg);
        } else {
            s = next(list, r, listarg);
            q = r;
        }
        if (! isvalid(list, s, listarg)) break;
        r = s;
    }
    for (; q != next(list, head(list, listarg), listarg); q = p) {
        p = head(list, listarg);
        for (s = next(list, p, listarg); s != q; s = next(list, p, listarg)) {
            if (issup(p, s, arg)) {
                swap(list, p, s, listarg);
            } else {
                p = s;
            }
        }
    }
}

単に、リスト走査中の交換の有無情報を保持する変数bに関する記述を取り除いただけである。
これをリンクした#65のコードを実行すると、

10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
#comparisons=45, #swaps=45
1 2 3 4 5 6 7 8 9 10
#comparisons=45, #swaps=0

降順リストを昇順に整列する場合も昇順リストを昇順に整列する場合も45回の比較が行われる。
listsortで無用な比較が行われていた時には#65の結果のように53回であった。