休日プログラミング..計数ソートとバケットソート

さて、前回はクイックソートをやりましたね。今回はこれからソートする数がある程度検討がつく場合には、クイックソートよりも速いアルゴリズムを作っていきたいと思います。
細かいことはコメントに書いてあります。

#計数ソート：1~kまでの値がソートされるということが前提。

def counting_sort(a)

  k = a.max

  b=Array.new(a.length)

  c=Array.new(k,0)

  #１〜ｋのそれぞれが何個あるかをｃに入れていく。

  a.each do |j|

    c[j-1]=c[j-1]+1

  end

  #一個前を足していくことで、各値をどこの配列番号に挿入

  #するかを知ることができる。

  for i in 1..k-1 do 

    c[i]=c[i]+c[i-1]

  end

  #後ろから入れていく。

  (a.length-1).downto(0) do |j|

    b[c[a[j]-1]-1]=a[j]

    c[a[j]-1]=c[a[j]-1]-1   #同じ値の時は一個前の配列に入れる

  end

  p b

end
#バケットソート。値が0~1の間にあると仮定する。

def bucket_sort(a)

 n=a.length-1

 b=Array.new(10){Array.new(0)}

 #0~9までの範囲に分類。

 for i in 0..n do

   c=(a[i]*10).truncate

   b[(a[i]*10).truncate]<<(a[i])

 end

 #ある程度ソートされている場合は挿入ソートが速い。

 for i in 0..n do

   insert_sort(b[i])

 end

 p b.flatten

end
a=[7,1,3,1,2,4,4,6,2,4,3]

counting_sort(a)
a=[0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68]

bucket_sort(a)

バケットソートの途中に挿入ソート使うので、これは前回作ったものをそのまま利用。計数ソートってなんか使えると思う。ある程度値が離れていないソートならこれを使っていった方がいいですな。


んで、これを作ってる間に詰まったことがある。Rubyの2次元配列は毎回この問題で悩むような気がしてならんｗ

#よくありがちな2元配列のミス

a=Array.new(5,Array.new)

これだと、それぞれのArrayの参照が同じ（個人的な見解）になっちゃうので、例えばa[2].push(15)とかやってみると、a[0]〜a[4]全てに15がプッシュされちゃうんです。これ最初にやってしまうとかなーり原因がわかりにくい。

#こうすべき。

a=Array.new(5){Array.new(0)}

ブロックにしてその中に別々の配列を作るっぽいです。こうすれば別々の配列ができて思い通りにプログラミングができます^^


それにしても、Rubyは何をやるにしても配列で解決できちゃいますよね。ホントはリストにして作るべきプログラミングだったんだけど、そんなの全く必要なし。快適です。