sortしてみた

作った物

• bubble_sort
• merge_sort

code

class Array
  def bubble_sort
    i=0; max_index=self.size-1
    each_index do |i|
      #p i
      return self if i >= max_index
      if self[i] > self[i+1]
        self[i],self[i+1]=self[i+1],self[i]
        i = 0
        retry
      end
      i += 1
    end
  end

   def merge_sort!(a=self,&block)
     return a if a.size <= 1
     cond = lambda {|x,y| x <= y} # unless block_given?
     def merge(left,right,&cond)
       tmp=[]
       loop do
         unless left.empty? || right.empty?
           tmp << (cond.call(left.first,right.first) ? left.shift : right.shift)
         else
           tmp << (left.empty? ? right : left)
           break
         end
       end
       tmp.flatten
     end
     n=a.size/2
     left=merge_sort!(a[0..n-1],&cond)
     right=merge_sort!(a[n..-1],&cond)
     merge(left,right,&cond)
   end

  def randomize
    each_index { |i| j=rand(i+1); self[i],self[j]=self[j],self[i]}
  end
end

#require  'benchmark'
# Benchmark.bmbm do |x|
#   a=(1..10000).to_a.randomize
#   x.report("quick") { a.dup.sort}
#  # x.report("bubble") { a.dup.bubble_sort}
#   x.report("merge") { a.dup.merge_sort!}
# end

merge_sortのところで、何故かブロックがうまく渡せていない。(あとで調べる)

結果

Rehearsal -----------------------------------------
quick   0.010000   0.000000   0.010000 (  0.003665)
merge   1.580000   0.240000   1.820000 (  1.876822)
-------------------------------- total: 1.830000sec

            user     system      total        real
quick   0.000000   0.000000   0.000000 (  0.003441)
merge   1.630000   0.170000   1.800000 (  1.912991)
>Exit code: 0

bubble_sortは200ぐらいから待つのが面倒になった。

感想

クイックソート早い。