基数ソート（Ruby） - Camera Obscura

基数ソートは固定長の文字列のソートなどに使うアルゴリズムで、下の位（文字列の右の方）から順にソートしていって、すべての位をソートし終えたとき、全体のソートが終っているという方法です。個々のソートには高速な「計数ソート」を使うとよい（「安定的な」ソートを使わねばなりません）。

Ruby でコーディングしてみました。
radix_sort.rb

class Array
  def counting_sort
    #Integer{a1[], s, m, equal[]}, String{a2[], result[]}
    
    a1, a2 = self[0], self[1]
    s = a1.size
    m = a1.max + 1
    equal = Array.new(m, 0)
    
    s.times {|i| equal[a1[i]] += 1}
    
    equal[-1] = 0
    (m - 1).times {|i| equal[i] += equal[i - 1]}
    
    result = Array.new(s)
    s.times do |i|
      result[equal[a1[i] - 1]] = a2[i]
      equal[a1[i] - 1] += 1
    end
    result
  end
  
  def radix_sort
    #String{self[]} -> Integer{ar[]} >> [String]
    st = self
    n = st[0].length
    n.times do |i|
      ar = st.map {|x| x[n - 1 - i].bytes[0]}
      st = [ar, st].counting_sort
    end
    st
  end
end

st = []
9.times {st << ("0".."9").to_a.sample(5).join}

p st
p st.radix_sort

実行例。

$ ruby radix_sort.rb
["24685", "74186", "81935", "17042", "74395", "72506", "52381", "78359", "10372"]
["10372", "17042", "24685", "52381", "72506", "74186", "74395", "78359", "81935"]