天泣記

ふと、in-place で radix sort ができるか調べてみると、1bit 単位で quick sort みたいなことをすればできるようだ。

試しに書いてみた。

def inplace_radix_sort(ary)
  max = 0
  ary.each {|v|
    unless v.is_a? Integer
      raise ArgumentError, "non-integer element"
    end
    if v < 0
      raise ArgumentError, "negative integer"
    end
    if max < v
      max = v
    end
  }
  inplace_radix_sort_internal(ary, 1 << (max.bit_length-1), 0, ary.length-1)
  ary
end

def inplace_radix_sort_internal(ary, mask, i0, j0)
  if mask == 0
    return
  end
  i = i0
  j = j0
  while i <= j
    if ary[i] & mask == 0
      i += 1
    elsif ary[j] & mask != 0
      j -= 1
    else
      ary[i], ary[j] = ary[j], ary[i]
      i += 1
      j -= 1
    end
  end
  # assert i == j+1
  mask >>= 1
  inplace_radix_sort_internal(ary, mask, i0, i-1)
  inplace_radix_sort_internal(ary, mask, j+1, j0)
end

ary = (0...10).to_a.shuffle
p inplace_radix_sort(ary) #=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

再帰の深さは最大要素のビット数で、それぞれの深さにおいて結局は全ての要素を調べるので、O(n log max) か。

複数ビット単位でやるには、入れ替える前に要素の数を数えておけば可能なようだ。

天泣記

2015-04-09 (Thu)