メモリ消費量を無視したquicksort

ブロック渡しの練習に良いかもしれない。 >準備運動のメニュー

class Array
  def qsort(a=self)
    return a if a.size<=1
    x=a.shift
    qsort(a.select{ |e| e <= x}).concat([x]).concat(qsort(a.select{ |e| x < e}))
  end

  def qsort2(a=self, &b)
    b = proc{ |e, x| e <= x} if b.nil?
    qs(a.dup,&b)
  end
  
  def qs(a, &b)
    return a if a.size <= 1
    x = a.shift
    qs(a.select{ |e| yield(e,x)}, &b).concat([x]).concat(qs(a.reject{ |e| yield(e,x)}, &b))
  end
end
p a = (1..20).map{ |e| (100*rand).to_i}
p a.qsort2{ |e, x| e >= x}
p a 
# >> [1, 68, 85, 0, 69, 87, 99, 86, 3, 94, 95, 57, 2, 7, 31, 51, 9, 28, 61, 2]
# >> [99, 95, 94, 87, 86, 85, 69, 68, 61, 57, 51, 31, 28, 9, 7, 3, 2, 2, 1, 0]
# >> [1, 68, 85, 0, 69, 87, 99, 86, 3, 94, 95, 57, 2, 7, 31, 51, 9, 28, 61, 2]

M-x xmp便利。

a.shiftのところ

下のような感じに変えた方が良いかもしれない。

x=a.delete(a[(rand a.size).to_i])

deleteじゃなくて

slice!を使った方が良いかも

x = a.slice!(rand(a.size))
#slice(1.4444) == slice(1)　だったなんて知らなかった。