単連結リストの整列 #91 バケツソートによる基数ソート

これまで、基数ソートにおけるステップごとの整列アルゴリズムに隣接交換法を使ってきた。
そのためこの基数ソートは要素数の二次オーダ、もしくはリストの実装次第ではそれ以上の時間計算量となる。
今回は、in-placeな整列という前提を崩すことになるが、
もっと時間計算量のオーダの小さいアルゴリズムをステップごとの整列に使ったものを作ってみる。

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

static intlist_t rsort(intlist_t list, int n)
{
    int i, s;
    intlist_t bucket[16], prev_list = list;
    for (i = 0, s = 0; i < n; i++, s += 4) {
        int k;
        intiter_t iter;
        intlist_t next_list = intlist_new();
        for (k = 0; k < 16; k++) bucket[k] = intlist_new();
        iter = intlist_iterator(prev_list);
        while (intiter_has_next(iter)) {
            int v = intelem_get_val(intiter_next(iter));
            intlist_add_first(bucket[((unsigned int)v >> s) & (16 - 1)], v);
        }
        intiter_dispose(iter);
        for (k = 16 - 1; k >= 0; k--) {
            intiter_t it = intlist_iterator(bucket[k]);
            while (intiter_has_next(it)) {
                intlist_add_first(next_list, intelem_get_val(intiter_next(it)));
            }
            intiter_dispose(it);
        }
        if (prev_list != list) intlist_dispose(prev_list);
        prev_list = next_list;
        for (k = 0; k < 16; k++) intlist_dispose(bucket[k]);
    }
    return prev_list;
}

static int nstep(void)
{
    int i, n = 0;
    for (i = RAND_MAX; i != 0; i /= 16) n++;
    return n;
}

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');
}

static void check(intlist_t list)
{
    int pv;
    intiter_t i = intlist_iterator(list);
    if (intiter_has_next(i)) {
        pv = intelem_get_val(intiter_next(i));
        while (intiter_has_next(i)) {
            int v = intelem_get_val(intiter_next(i));
            assert(pv <= v);
            pv = v;
        }
    }
    intiter_dispose(i);
}

int main(void)
{
    int i;
    intlist_t list = intlist_new(), sorted;
    srand(7654321);
    for (i = 0; i < 20; i++) intlist_add_first(list, rand());
    print(list);
    sorted = rsort(list, nstep());
    print(sorted);
    check(sorted);
    intlist_dispose(list);
    intlist_dispose(sorted);
    return 0;
}

このコードは整数を格納するリストのインタフェイスintlistの範囲内で、
0以上RAND_MAX以下の範囲を値とする乱数列を基数ソートによって昇順に整列する。

intlistはリストを変更する操作としては、新規に要素を加えること、
リスト全体を破棄すること、整列関数listsortで整列すること以外に無い。
そこで、listsortを介さないで整列する場合は、
オリジナルのリストの要素と同値のコピーをもち整列されたリストを作成して返すことになる。

基数ソートの各ステップにはバケツソートを利用しており、16進数一桁ごとのバケツソートを行う。
16個のバケツbucket[16]を用意し、抽出した一桁に対応したバケツに要素のコピーを放り込む。
これを引数で指定されたnステップ行えば整列は終了する。
このステップ数はint型で表現できる最大の正の整数の16進数表現の桁数とすればいい。
しかし、RAND_MAXを超える値の要素はないためRAND_MAXの桁数で十分である。
前日の結果によればUbuntu+glibcではこの二つは同じ8ステップになるが、
MinGW+msvcrtでは8ステップでなく4ステップで十分ということになる。

WindowsXPにおける実行結果は、

21554 8771 16254 6480 11199 18563 15450 21395 25317 18922 18328 26369 30292 27959 14730 17062 24687 12527 28734 26614
6480 8771 11199 12527 14730 15450 16254 17062 18328 18563 18922 21395 21554 24687 25317 26369 26614 27959 28734 30292

Ubuntuでは、

131391885 870363153 1299100705 2068425484 1549062271 595077934 1044385092 1886785879 203200482 86018122 1096858338 58793833 1029739795 1823611321 1735752266 2042774023 2039418097 779178976 1398738163 705062050
58793833 86018122 131391885 203200482 595077934 705062050 779178976 870363153 1029739795 1044385092 1096858338 1299100705 1398738163 1549062271 1735752266 1823611321 1886785879 2039418097 2042774023 2068425484

結果は整列している感じだが、本当に昇順に整列しているのか見づらい……
が、コードでは整列できていることを確認する関数checkで整列済みリストをチェックしており、
この関数内のassertに失敗していないことから整列はできているのだろう。

使用しているリストのインタフェイスの制約からオリジナルのリスト自身を整列できないことは上で述べた。
実のところ、リストの要素間のリンクを基数ソートのステップごとの整列機能実装側が触れるのであれば、
上のコードのような要素数に比例した別メモリが必要なものではなく、
定数サイズの作業用メモリだけで済むin-placeなアルゴリズムにすることができる（はず）。
しかしこれも要素への操作の自由度の低いintlistのインタフェイスの範囲内では非in-placeにせざるを得ないと思う。