単連結リストの整列 #65 回数を計ってみる - 借りてきた猫のように静か

さて、intlistを使ってみよう。

#include <stdio.h>
#include "intlist.h"

#define UNUSED_ARG(x) (void)(x)

static int issup(cintelem_t p, cintelem_t q, void *arg)
{
    UNUSED_ARG(arg);
    return intelem_get_val(p) > intelem_get_val(q);
}

static intlist_t make(void)
{
    int i;
    intlist_t list = intlist_new();
    if (list != NULL) for (i = 1; i <= 10; i++) intlist_add_first(list, i);
    return list;
}

static void print(intlist_t list)
{
    intiter_t i = intlist_iterator(list);
    while (intiter_has_next(i)) {
        cintelem_t e = intiter_next(i);
        printf("%d ", intelem_get_val(e));
    }
    intiter_dispose(i);
    putchar('\n');
}

int main(void)
{
    intlist_t list = make();
    print(list);
    intlist_sort(list, issup, NULL);
    print(list);
    printf("#comparisons=%lu, #swaps=%lu\n", intlist_get_compare_counts(list), intlist_get_swap_counts(list));
    intlist_reset_counts(list);
    intlist_sort(list, issup, NULL);
    print(list);
    printf("#comparisons=%lu, #swaps=%lu\n", intlist_get_compare_counts(list), intlist_get_swap_counts(list));
    intlist_dispose(list);
    return 0;
}

1から10までの整数値を先頭から降順に持つ要素数10のリストを生成し、
まず昇順に整列し、その整列に要した要素の比較と交換の回数を表示する。
次にその昇順に整列済みのリストを再度昇順に整列し、この時の比較、交換の回数を表示する。

実行すると、

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

あっれー？降順のリストを昇順に整列する時の比較回数と交換回数が異なっているよ？
隣接交換法で昇順に整列する場合、降順に整列済みのデータが最も要素の交換の回数が多くなる最悪ケースとなる。
隣接交換法はリストの後方に昇順に整列済みの値の大きな要素が順番に集まっていくので、
昇順に整列済みの部分を要素の比較の対象から外すようにコードを組んだ場合は、
要素の比較の回数と要素の交換の回数が同じになるはずである。

既に昇順に整列しているものを昇順に整列する場合は、
隣り合う要素同士の比較が一通り行われた後、一度も交換されなかったのでそのまま整列処理は終了と判断される。
これが#58でlistsortに施した変更の核の部分であり、
実際、上の結果では要素数10の時の隣接要素間の数9が比較回数9となって現れており、この時の交換回数は0回である。

降順のものを昇順にする場合は、
最初は未整列であるので9回の比較が必要であり、
次は既に最大値となっているリスト末尾を除き、8回の比較が必要になる。
順次必要な回数が減って行き、最後はリスト先頭とその次の要素との比較が1回行われて終了となる。
したがって、必要な比較回数（必要な交換回数でもある）は1から9までの総和で45回である。
上の実行結果では交換回数は45回になっているが、比較回数がそれより8回多くなっている。

変更前のlistsortとリンクして実行してみた。

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

変更前の場合は整列済みでも最後まで比較だけは行われるので降順→昇順も昇順→昇順も同じ比較回数になる。
確かに回数は同じなのだが、理論値よりも比較回数が多い。
何かがおかしい値ではあるが、その値はlistsortの変更前後で同じなので、
おかしい部分はlistsortの変更前からあったと考えられる。
もう一つの可能性であるintlistの実装についてはおかしいというわけではないと思う。
intlistではlistsortからの呼び出し1回に対して複数回になるような処理はしていないからである。
つまり、最初に関数listsortを作成した#34の時からこれは存在していたのではないかという気がする。

比較回数が理論値よりも多いものの、交換回数は理論通りであるし、
今回の整列結果も含めてこれまでlistsortによる整列結果に誤ったものはなかったと思う。
何らかの不要な比較を行っており、その比較は交換を必要としない偽の結果となっているのだろうと推測される。