単連結リストの整列 #88 負数も含めた桁数制限のある整数の整列

これまで3桁の自然数という範囲にリスト要素の値がある場合の基数ソートだったが、
桁数に制限は付くのは同じだが負の場合も含む整数値に拡大した時の整列について。
とりあえず10進数一桁を単位とする基数ソートで行ってみる。

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

static int issup(cintelem_t p, cintelem_t q, void *base)
{
    if (base == 0) {
        return intelem_get_val(p) >= 0 && intelem_get_val(q) < 0;
    } else {
        int ip = intelem_get_val(p), iq = intelem_get_val(q);
        ip = ip >= 0 ? ip / (int)base % 10 : (10 - 1) - (-ip) / (int)base % 10;
        iq = iq >= 0 ? iq / (int)base % 10 : (10 - 1) - (-iq) / (int)base % 10;
        return ip > iq;
    }
}

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

int main(void)
{
    int i;
    intlist_t list = intlist_new();
    srand(100);
    for (i = 0; i < 20; i++) intlist_add_first(list, (int)(rand() / (RAND_MAX + 1.0) * 1999) - 999);
    print(list);
    intlist_sort(list, issup, (void *)1);
    print(list);
    intlist_sort(list, issup, (void *)10);
    print(list);
    intlist_sort(list, issup, (void *)100);
    print(list);
    intlist_sort(list, issup, (void *)0);
    print(list);
    return 0;
}

整列は一の位、十の位、百の位と進み、最後に符号のみによる整列を行って終了する。
順位定義関数issupは、baseに0が与えられると、非負数が負数よりも上位であるという定義に基づいた結果を返す。
baseが正数の場合、比較対象が正数の時に10進数でbaseの位のみの大小関係で順位の上下を判断するのは今まで通りだが、
比較対象が負数の時は、対象の一桁を取り出した後に9から引いている。
負数ではのような順位になっているとみなせるからである。
そのため、9から対象の一桁を引いて順位を逆転している。
実行すると、

-521  357 -937 -770 -205 -296    8  195  983  454 -656  416 -896  507 -313  495   20 -669 -925 -977
  20 -669 -937 -977 -296  983 -656 -896 -205  454 -925  195  495  416 -313  357  507 -521    8 -770
-296 -896  507    8  416   20 -977 -770 -669 -656  454  357 -937 -925 -521  983 -313 -205  195  495
   8   20 -977 -937 -925 -896  195 -770 -669 -656  357  416  454 -521  495  507 -313 -296 -205  983
-977 -937 -925 -896 -770 -669 -656 -521 -313 -296 -205    8   20  195  357  416  454  495  507  983

最上段のオリジナルリストが最下段のように昇順に整列する。
一の位だけで整列した第二段の最初の方のように、20の0と-669の9とは同順位である。