単連結リストの整列 #66 何が無用な比較か見てみる

C

推測にしたがって何と何を比較しているかの詳細を見てみる。
そのために前回のコードで整列用に提供している順位定義関数issupに一文付け加える。

...snip
static int issup(cintelem_t p, cintelem_t q, void *arg)
{
	UNUSED_ARG(arg);
	printf("issup: %d, %d\n", intelem_get_val(p), intelem_get_val(q));
	return intelem_get_val(p) > intelem_get_val(q);
}
...snip

実行すると、

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

どうやら最初のループ以外でループの最後に無用な比較が行われているようだ。

...snip
issup: 9, 10
...snip
issup: 8, 9
...snip
issup: 7, 8
...snip
issup: 6, 7
...snip
issup: 5, 6
...snip
issup: 4, 5
...snip
issup: 3, 4
...snip
issup: 2, 3
...snip

このどれもが第一引数よりも第二引数の方が上位にありissupは偽を返すため交換は行われない。
例えば、二回目のループの最後の比較である

issup: 9, 10

ならば、この10の値を持つ第二引数は一回目のループでリスト中の最大値としてリスト末尾に移され、
本来二回目以降ループでの比較には現れることはない要素である。
他の第二引数も同じ性質のものであり、末尾寄りに集められた整列済み要素列の先頭の要素となっている。
つまり、本当ならこれらの一つ前でループは終了すべきなのに一回多目に回ってしまっている。
要素数10のリストの場合、9回回るループのうち最初のループ一回を除いて一回ずつ多く比較しており、
本来45回の比較回数が(9-1)回多い53回になっていたようだ。
この比較はする必要がないというだけの比較であり、比較してしまっても整列結果には影響を与えない。
が、する必要がないのでやらせていないと思っていたにも関わらず行ってしまっているのは気持ち悪い。
無用な比較をしないように変更してみよう。