基数ソートと計数ソート - 忘れても大丈夫

問題. 自然数列の整列

要素数 $d$ 以下の $n$ 個の自然数列 $A_1 = (a_{1,1}, a_{1,2}, \ldots, a_{1,d_1}), \ldots, A_n = (a_{n,1}, a_{n, 2}, \ldots, a_{n, d_n})$ が与えられる．これらを辞書式順に昇順に整列せよ．ただし， $A_i < A_j$ であるとは， $A_i$ が $A_j$ の先頭部分に一致するか，または， $t$ を $a_{i, t} \neq a_{j, t}$ となる最小の添字としたときに $a_{i, t} < a_{j, t}$ となることである．

制約： $1 \le a_{i, j} \le k$

例. $A_1 = (3), A_2 = (1, 2), A_3 = (3, 1, 1), A_4 = (3, 2), A_5 = (1, 3, 2), A_6 = (1, 3), A_7 = (2)$
昇順に整列すると $A_2 < A_6 < A_5 < A_7 < A_1 < A_3 < A_4$ となる．

解法. 基数ソート (radix sort)

基数ソートでは部分的に計数ソート（counting sort）を用いるために，初めに計数ソートの説明を行い，その後で基数ソートの説明を行う．

計数ソート（counting sort）

$n$ 個の自然数 $a_0, a_2, \ldots, a_{n-1}$ を計数ソートで昇順にソートする（下の疑似コードに合わすために0-indexにした）．ここで， $0 \le a_i \le k$ として， $k \le n$ と仮定する．要素の値が小さいことに着目して，各要素に対して自身の値より小さい要素数を数えることにする．これは累積和を用いると，計算時間と領域量は互いに $O(n + k)$ で求めることができる．

// 入力
const int n = 8;
vector<int> a = {4, 1, 2, 6, 4, 1, 1, 0};

// 自身の値より小さな要素数を数える
int k = *max_element(a.begin(), a.end());
vector<int> cnt(k + 1);
for (int i = 0; i < n; ++i) ++cnt[a[i]];
for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
// cnt = (1, 4, 5, 5, 7, 7, 8)

次に，各要素について自身がソート後に何番目の位置に移動するかを考えると， $a_i$ の位置は区間 $\left[cnt(a_i - 1), cnt(a_i) \right)$ に含まれることが分かる．ただし，基数ソートで使用するために安定性（stability）を満たすように位置決めを行う必要がある．一般的にソートが安定であるとは，等しい要素の順番を入力前と同じに保つ性質のことである．安定性を満たすために，後ろの要素から順番に自身が入る場所を見つける．このとき， $cnt(a_i) - 1$ 番目に挿入して $cnt(a_i)$ の値を1つ減らすと安定性を満たすように全ての要素を整列することができる．
以上から，計数ソートは全体で $O(n + k)$ の時間と領域で求めることができる．

vector<int> b(n); // aのソーティング後の要素
for (int i = n - 1; 0 <= i; --i) {
    b[cnt[a[i]] - 1] = a[i];
    --cnt[a[i]];
}
// b = (0, 1, 1, 1, 2, 4, 4, 6)

基数ソート

$d = \max\{d_1, d_2, \ldots, d_n\}$ とする．与えられた自然数列全体を $d$ 番目の要素から降順に計数ソートをする． $j$ 番目の要素に着目しているときに $d_i < j$ となる自然数列 $A_i$ に対しては $j$ 番目の要素が存在しないので，すべての数列の要素の最小値より小さな値とする．ここでは便宜的に $a_{i,j} = 0$ とする．
以上より，基数ソートは $d$ 回の計数ソートを行うので，全体で $O(d (n + k))$ 時間で計算することができる．
初めの例に対する実行結果は次のようになる．
f:id:tatanaideyo:20180915144317p:plain

まとめ

要素対の比較を行う比較ソートアルゴリズムは最悪時に $\Omega(n \log n)$ 回の比較を行うが，基数ソートも計数ソートも比較ソートアルゴリズムではないので下界を打ち破ることができる．
基数ソートは木の同型性判定で， $O(n \log n)$ 時間から $O(n)$ 時間にするときに用いられる．