単連結リストの整列 #87 十進一桁で行う必要はない

前回、十進数での一桁単位で基数ソートを行ったわけだが、
別に十進数一桁でなければならないなんてことはない。

...snip
static int issup(cintelem_t p, cintelem_t q, void *base)
{
    return intelem_get_val(p) / (int)base % 16 > intelem_get_val(q) / (int)base % 16;
}
...snip
int main(void)
{
...snip
    print(list);
    intlist_sort(list, issup, (void *)1);
    print(list);
    intlist_sort(list, issup, (void *)16);
    print(list);
    intlist_sort(list, issup, (void *)256);
    print(list);
...snip
}

のように16進数一桁*1単位で行うこともできる。
実行結果は、

315 710 128 203 457 416 553 637 992 754 254 737 146 778 409 773 558 248 133 110
128 416 992 737 754 146 773 133 710 248 457 553 409 778 315 203 637 254 558 110
773 778 553 558 315 110 637 128 133 146 409 416 710 457 203 992 737 754 248 254
110 128 133 146 203 248 254 315 409 416 457 553 558 637 710 737 754 773 778 992

前回のように十進数の桁ごとの整列であれば桁に注目することで整列していく様子が見えるのだが、
4ビット単位で整列していくと途中経過が意味不明に並べ替えられて、
最後にいきなり整列した結果が表示されるので面食らう。
これは表示が十進数なのでそう見えるだけで、

...snip
static void print(intlist_t list)
{
...snip
        printf("%03x ", intelem_get_val(e));
...snip
}
...snip

のように16進数表示にしてやれば、

13b 2c6 080 0cb 1c9 1a0 229 27d 3e0 2f2 0fe 2e1 092 30a 199 305 22e 0f8 085 06e
080 1a0 3e0 2e1 2f2 092 305 085 2c6 0f8 1c9 229 199 30a 13b 0cb 27d 0fe 22e 06e
305 30a 229 22e 13b 06e 27d 080 085 092 199 1a0 2c6 1c9 0cb 3e0 2e1 2f2 0f8 0fe
06e 080 085 092 0cb 0f8 0fe 13b 199 1a0 1c9 229 22e 27d 2c6 2e1 2f2 305 30a 3e0

のように一桁ごとに昇順に整列していく様子が見えてくる。

*1:2進数四桁と言ってもいいし、他の言い方もできる