パンチカードを並べ替える

Ruby で遊ぶネタが他にないかな、と思っていたら、子供の頃パンチカードを作って遊んだのを思い出しました。
数字を書いたカードの上部に穴を開け、２進数でその数字を示せるように、パンチカードに切り欠きを入れます。
たとえば２のカードは、右から２番目の穴の上を切って溝に、３のカードは１番右と２番目の穴を切ります。
そうしておくと、竹串を順番に穴を通して引っかかったカードだけを並べ替えていくと、カードを順番に並べることができるというもの。

これを書いてみました。
まずカードを前後に動かす操作。b が穴の場所を示す２進数です。

def put_forward(array, b)
  int_array_1 = []
  int_array_2 = []
  for i in array
    if i & b == b
      int_array_1.push(i)
    else
      int_array_2.push(i)
    end
  end
  int_array_1 += int_array_2
end

def put_backward(array, b)
  int_array_1 = []
  int_array_2 = []
  for i in array
    if i & b == b
      int_array_2.push(i)
    else
      int_array_1.push(i)
    end
  end
  int_array_1 += int_array_2
end

こうしておいて、

int_array_ordered = 1..31
int_array_rand = int_array_ordered.sort_by{rand}
int_array_new = int_array_rand.dup

for i in [0b00001, 0b00010, 0b00100, 0b01000, 0b10000]
    int_array_new = put_backward(int_array_new, i)
end

print int_array_ordered, "\n"
print int_array_rand, "\n"
print int_array_new, "\n"

とするとちゃんとソートされていることがわかります。
調べると、基数ソートという名前がついているようですね。

一応こんな関数を書くとソートできます。

def punchcardsort(array)
  len = (array.max).to_s(2).length
  sort_key = []
  for i in 1..len
    sort_key.push(2**i)
  end
  for i in sort_key
    array = put_backward(array, i)
  end
  return array
end

しかしもちろん、ruby に用意されている sort を使った方がずっと速いようです。