基数ソートのプログラムです。
# 基数ソート (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 # 基数ソート (基数交換法1) 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 # 基数ソート (基数交換法2) 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