単連結リストの整列 #86 安定性を利用する

C

同じ順位の要素の順序が入れ替わっても別に問題ないと言われればそうなのだが、
整列法が安定であると便利な使い方もできる。

3桁の自然数が収められたリストを昇順に整列することを考える。
これはこれまでやってきたことであり、
普通に各要素の自然数間の大小関係を評価する関数を整列関数に与えてやればいい。
が、ここでは少し別の方法をとることにする。

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

static int issup(cintelem_t p, cintelem_t q, void *base)
{
    return intelem_get_val(p) / (int)base % 10 > intelem_get_val(q) / (int)base % 10;
}

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)
{
    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) * 900) + 100);
    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);
    return 0;
}

とりあえず、ポインタ型のサイズがint型を格納するに十分なものであること前提のコードである。

順位定義関数issupは、二つの要素に格納された自然数を比較する際に、
エクストラデータとして与えられるint型の変数baseで決まる位の桁の数字だけを比較する。
つまり、例えば整数値932と178の比較においてbaseに10が与えられれば、
二つの自然数の十の位、つまり、3と7で両者を比較する。
したがって、932よりも178の方が十の位だけを見れば順位は上位になる。
上の実装では、各位ごとに別の順位定義関数を用意してもいいのだが、
エクストラデータはこれまでUNUSED_ARGばかりしていて使ったことがなかったので使ってみた。

整列法は与えられたリストをまず一の位で整列し、続いてそれを十の位で整列し、
さらにその結果を百の位で整列する。いわゆる基数ソートと呼ばれる方法である。
基数ソートは各桁ごとの整列法にバケツソートなどの高速なアルゴリズムを使うことで、
空間計算量と時間計算量の双方をうまくバランスをとって低減化できる方法である。
しかし、そういった性能を気にしなければ各桁ごとの整列に用いる整列法は、
ある性質さえ持っていればどんなものを使っても問題ない。
その性質こそが整列の安定性である。

安定な整列である隣接交換法による実装を上のコードにリンクして実行すると、

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

一番上が元データ、次が一の位での昇順整列の結果、その結果を十の位で整列した結果がその次、
さらにその結果を百の位で整列した結果が一番下である。
途中の結果は一見するとあまり整列しているように見えないが、
最終的には昇順に整列できている。

これに対して、安定性を欠く基本選択法による実装をリンクして実行すると、

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

百の位については整列しているので大雑把には昇順に並んでいるように見えなくはない。
しかし、実際にはうまく整列していないことが分かる。

基数ソートは安定な整列法を利用しなければうまく働かない。