基数ソートのプログラムです。
# 基数ソート (32 bit 無符号整数専用)
def radix_sort(buff)
count = Array.new(256)
cumul = Array.new(256)
work = Array.new(buff.size)
# 1 byte ずつ分布数えソート
for i in 0 ... 4
shift = i * 8
count.fill(0)
buff.each do |x|
count[(x >> shift) & 0xff] += 1
end
sum = 0
for x in 0 ... 256
sum += count[x]
cumul[x] = sum
end
x = buff.size - 1
while x >= 0
y = (buff[x] >> shift) & 0xff
cumul[y] -= 1
work[ cumul[y] ] = buff[x]
x -= 1
end
temp = buff
buff = work
work = temp
end
end
# 基数ソート (基数交換法１)
def radix_sort2(buff, low, high, n)
return if low >= high || n == 0
i = low
j = high
loop do
i += 1 while i <= j && buff[i] & n == 0
j -= 1 while i <= j && buff[j] & n > 0
break if i > j
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
end
radix_sort2(buff, low, j, n >> 1)
radix_sort2(buff, i, high, n >> 1)
end
# 基数ソート (基数交換法２)
def radix_sort3(buff, low, high, n)
return if n == 0
if high - low <= LIMIT
insert_sort2(buff, low, high)
return
end
i = low
j = high
loop do
i += 1 while i <= j && buff[i] & n == 0
j -= 1 while i <= j && buff[j] & n > 0
break if i > j
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
end
radix_sort3(buff, low, j, n >> 1)
radix_sort3(buff, i, high, n >> 1)
end
マルチキークイックソート (Multikey Quicksort) は 1997 年に Jon Bentley と Robert Sedgewick が発表した文字列のソートに適した高速なアルゴリズムです。マルチキークイックソートで文字列をソートする場合、普通のクイックソートと大きく異なる点が 2 つあります。ひとつは文字単位で比較を行うことです。文字列をソートする場合、一般的なソートは文字列単位で比較を行います。ところが、マルチキークイックソートは最初に 1 文字目を比較してソートを行い、ソートが完了しない場合（同じ値が複数ある場合）は、さらに 2 文字目を比較してソートを行う、というように先頭から順番に文字を比較してソートを行います。
もうひとつは区間の分け方です。普通のクイックソートは枢軸を基準にして、小さいデータと大きいデータの 2 つの区間に分割していくことでソートを行います。マルチキークイックソートは枢軸を基準にするところは同じですが、区間を 2 分割するのではなく、小さいデータ、枢軸と等しいデータ、大きいデータの 3 分割にするところが特徴です。このため、マルチキークイックソートは Ternary Quicksort とも呼ばれています。
たとえば、n 番目の文字を比較して区間を 3 分割したとしましょう。小さいデータと大きいデータの区間は n 番目の文字でソートを続行すればいいですね。これは普通のクイックソートと同じです。枢軸と等しいデータが複数ある場合、n 番目の文字ではソートが完了しないので、次は n + 1 番目の文字を比較してソートを行います。このように枢軸と等しいデータを集めることで、その区間は次の文字へ進めることができるわけです。
このアルゴリズムを疑似コードでプログラムすると、次のようになります。
# Multikey Quicksort の擬似コード
def multikey_quicksort(low, high, n)
if 区間のデータ数が NUM 以下
単純なソートアルゴリズムに切り替えてソート
else
n 番目の文字で枢軸を選択して low - high を 3 分割する
(< : low - m1-1, = : m1 - m2-1, > : m2 - high)
multikey-quicksort(low, m1 - 1, n)
if n 番目の文字 != 終端記号
multikey-quicksort( m1, m2 - 1, n + 1 )
end
multikey-quick( m2, high, n )
end
end
マルチキークイックソートは再帰呼び出しを使うと簡単にプログラムできます。区間を low と high で表し、比較する文字の位置を n で表します。区間のデータ数が一定の個数 (NUM) 以下になったら、単純なソートアルゴリズムに切り替えます。この方が少しだけ速くなります。
n 番目の文字で区間を 3 分割したら、multikey-quicksort を再帰呼び出しします。このとき、枢軸より小さい区間 (low - m1-1) と大きい区間 (m2 - high) は n 番目の文字でソートを続行します。等しい区間 (m1 - m2-1) は n + 1 番目の文字へ進めてソートを行います。もしも、等しい区間の文字 (枢軸) が終端文字であれば、文字列を最後まで比較したので再帰呼び出しは行いません。つまり、同じ文字列が複数個あるということです。
文字列の比較関数 compare を用意して、クイックソートとマルチキークイックソートの実行速度を比較します。文字列の比較に時間がかかる場合はマルチキークイックソートの方が速いのですが、そうでない場合はクイックソートの方が速くなります。
#
# mqsort.rb : Multikey Quicksort
#
# Copyright (C) 2006 Makoto Hiroi
#
LIMIT = 10
# 文字列の終端を nil で判定する
def nil.coerce(n)
[n, -1]
end
def nil.-(n)
-1 - n
end
# 文字列の比較
def compare(s1, s2, depth = 0)
for x in depth .. s1.size
r = s1[x] - s2[x]
return r if r != 0
end
0
end
# 挿入ソート
def insert_sort(buff, low, high, depth = 0)
for i in low+1 .. high
temp = buff[i]
j = i - 1
while j >= low && compare(temp, buff[j], depth) < 0
buff[j + 1] = buff[j]
j -= 1
end
buff[j + 1] = temp
end
end
# クイックソート
def quick_sort(buff)
low_stack = []
high_stack = []
low = 0
high = buff.size - 1
loop do
loop do
if high - low <= LIMIT
insert_sort(buff, low, high)
break
end
p = buff[low + rand(high - low)]
i = low
j = high
loop do
i += 1 while compare(buff[i], p) < 0
j -= 1 while compare(buff[j], p) > 0
break if i >= j
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
end
if i - low > high - j
low_stack << low
high_stack << (i - 1)
low = j + 1
else
low_stack << (j + 1)
high_stack << high
high = i - 1
end
end
break if low_stack.empty?
low = low_stack.pop
high = high_stack.pop
end
end
# マルチキークイックソート
def mqsort(buff, low, high, depth)
if high - low <= LIMIT
insert_sort(buff, low, high, depth)
return
end
p = buff[low + rand(high - low)][depth]
# 最初は 4 分割
# low - m1-1 (p) | m1 - j | i - m2 | m2+1 - high (p)
i = m1 = low
j = m2 = high
while true
while i <= j
k = buff[i][depth] - p
break if k > 0
if k == 0
temp = buff[i]
buff[i] = buff[m1]
buff[m1] = temp
m1 += 1
end
i += 1
end
while i <= j
k = buff[j][depth] - p
break if k < 0
if k == 0
temp = buff[j]
buff[j] = buff[m2]
buff[m2] = temp
m2 -= 1
end
j -= 1
end
break if i > j
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
end
# 枢軸と等しいデータを中央に集める
k = if m1 - low < i - m1 then m1 - low else i - m1 end
for l in 0 ... k
temp = buff[low + l]
buff[low + l] = buff[j - l]
buff[j - l] = temp
end
m1 = low + (i - m1)
k = if high - m2 < m2 - j then high - m2 else m2 - j end
for l in 0 ... k
temp = buff[high - l]
buff[high - l] = buff[i + l]
buff[i + l] = temp
end
m2 = high - (m2 - j) + 1
# m1 - m2-1 が等しいデータ
mqsort(buff, low, m1 - 1, depth)
if buff[m1][depth]
mqsort(buff, m1, m2 - 1, depth + 1)
end
mqsort(buff, m2, high, depth)
end
if __FILE__ == $0
4.times do |i|
n = 2000 * (i + 1)
a = []
n.times do
a << rand(0xffffffff).to_s
end
print n, ": "
b = a.dup
s = Time.now
mqsort(b, 0, b.size - 1, 0)
e = Time.now
print e - s, " "
c = a.dup
s = Time.now
quick_sort(c)
e = Time.now
print e - s, "\n"
d = a.sort
print "error\n" if b != d || c != d
end
end
mqsort quick
--------------------
2000: 0.125 0.344
4000: 0.297 0.750
6000: 0.422 1.250
8000: 0.563 1.782