バケツソートとn log nの壁 - アルゴリズムクイックリファレンス４章の補足 -

概要

本を読んで勉強しなおし、気になったことを書くシリーズです。
今回は、アルゴリズムクイックリファレンス４章の「整列アルゴリズム」がテーマです。
比較を含むソートが$O(n\log n)$にならざるを得ないことと、比較を含まなければ$O(n\log n)$よりも早いソート方法が存在する、ということがメインテーマです。

比較の限界について

比較を含むソートの、（最悪の場合の）計算量が$O(n\log n)$より小さくなることはない、というのはよく知られた結果です。
これは、次のように考えれば明らかになります。

• 比較というオペレーションを$\mathrm{cmp}(a,b)$などと書くと、$a<b$または$a\geq b$という、二つの状態のいずれかを返します。つまり、$\mathrm{cmp}(a,b)$一回につき、$1\mathrm{bit}$の情報量がある、と考えることができます。
• $\mathrm{cmp}$を$m$回繰り返すことで、理論上の最大値として、$m\mathrm{bit}$つまり$2^m$の状態を区別することができます。
• 比較して順序を求めたい対象が$n$個の要素から為るとすると、そこに定義できる(全)順序は$n!$通りあります。
• $n!$の状態を区別するには、$\log_2 (n!)\mathrm{bit}$が必要となります。$\log_2 (n!)$はスターリングの公式により$n\log_2 n - O(n)$といった量になるので、比較を含む場合の理論的な最大計算量は$O(n\log n)$となります。

この一方で、比較が不要であれば、$n\log n$を簡単に超えることができます。

意外と自明なバケツソート

前置き

言われてみればその通りなのですが、例えば$1$から$10000$までのいずれかの値を、重複無しで取る、ということが分かっている、ランダム列$a_k,b_k(1\leq k \leq 10000)$があるとします。
このとき、$(a_k,b_k)$の組を、$a_k$の順でソートすることを考えます。
ここで、はじめに$n=10000$要素からなる配列$c_k$を作成して、$k=1$から順に、$c_{a_k}=b_k$という代入作業を繰り返せば、まさしく$a_k$でソートした列が手に入ってしまいます。
当然ですが、このソートは全体を一度処理すれば終わってしまうので、$O(n)$ですね。

発展形として、a_kの値が疎な場合、例えば$1\leq k \leq n/2$だが$a_k \in [1,n]$という場合も、上と同じ手順で「スカスカの」数列を作っておいてから、そのスカスカの数列を詰める作業をすればよく、やはり$O(n)$で処理できます。

バケツソート

この前置きと同じような考え方で、上でいう$c_k$として重複を許すようにしたものがバケツソートです。
つまり、$a_k$の取りうる値の範囲が決まっている前提で、$a_k \in [c_1,c_2)$なら$a_k$は$C_1$に属する、$a_k \in [c_2,c_3)$なら$a_k$は$C_2$に属する、…という考え方をします。
この場合は重複があり得ますが、重複したものについては、他のアルゴリズムでソートします。
これを用いると、$C_i$たちの取れる領域を広げられるならば、相当なパフォーマンスが期待できる、ということですね。$C_i$たちの重複がいつも小さい範囲であることが保証できれば、全体のパフォーマンスは$O(n)$と言えます。
以下、$b_k=a_k$とし、$a_k$が$0$から密に詰まっている場合を想定したバケツソートのソースです。都合により、$c_k$をb[k]と書いています。

bucket

def bsort(a) # 非破壊的
  l = a.length
  b = Array.new(l){0}
  for i in 0..(l-1) do
    b[a[i]] = a[i]
  end
  return b
end

では、実際にバケツソートのパフォーマンスを見てみます。
上のソースと、以前の破壊的なマージソートのパフォーマンスを比較してみます。
Rubyでバブルソートとマージソートを比較する

compare

# 乱数列の作成
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
N = 100000
target = Array.new(N){0}
n = -1
temp = Array.new(N){n;n+=1}
n += 1
while n > 0 do
  t = rand(n)
  n -= 1
  target[n] = temp[t]
  temp.delete_at(t)
end

targeta = target.clone
targetb = target.clone

timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
bsort(targeta)
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
msort(targetb)
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}

p timearr[1] - timearr[0]
p timearr[2] - timearr[1]
p timearr[3] - timearr[2]

結果

773380  # 準備の時間
14539   # バケツソート（無重複）の時間
253719  # マージソートの時間

当たり前といえば当たり前ですね。でも、要素の事前情報を使えば…というのは、ちゃんと考えたことがなかったので、へーと思いました。$O(n \log n)$という「標語」に踊らされてはいかんですね。

おまけ：ソートの安定性について

他の章もそうですが、４章は構成が練られており、挿入ソート、中央値ソートからの他のアルゴリズムへの展開は綺麗でわかりやすいと思います。読み物としても面白いのですが、このあたりの話は今回はばっさりと削って、ソートの安定性の話のみ少し記しておきます。

よく、エクセルなんかで並び替えを行う際、B列でソートしてからA列でソート、というオペレーションをすることがあります。例えばAに大分類、Bに小分類みたいなソートしたい項目が入っていて、大分類＞小分類の順でソートしたい時に有効な並び替え手法です。
しかし、このような手順でソートしたときに、大分類＞小分類の順で各行についての順序を定義してソートした場合の結果と一致するということは、自明なことではありません。
実際、A列で並び替えた結果、B列での並びが完全にでたらめになるようなアルゴリズムもいくつかあります。（著名な例：ボゴソート）

そこで、このようなソートの性質のことを「安定性」と呼び、上の手順によるソートで大分類毎の小分類の並び順が保存されるとき、そのソートは安定であるといいます。

おしまい

次は５章です。
ちなみに、このシリーズには、他に次のような記事があります。
【この記事→】バケツソートとn log nの壁 - アルゴリズムクイックリファレンス４章の補足 - ※Ruby
探索と計算の分割 - アルゴリズムクイックリファレンス５章の補足 - ※Python
Pythonで迷路を解く - アルゴリズムクイックリファレンス６章の補足 - ※Python
フォード・ファルカーソン法とその応用 - アルゴリズムクイックリファレンス８章の補足 - ※Python