Sort Algorithms in Ruby

sorts.rb

#!/opt/local/bin/ruby1.9
#-*-encoding: utf-8-*-
require "test/unit"

class Array
  def insert_sort
    inject([]) { |mem, var| mem.insert_with_order(var) }
  end

  def insert_with_order(item)
    pos = find_index { |n| item <= n } || length
    insert(pos, item)
  end

  def select_sort
    tmp = self.dup
    res = []
    res.push tmp.delete_min until tmp.empty?
    res
  end

  def delete_min
    min_idx = find_index { |item| item == self.min }
    delete_at(min_idx)
  end

  def bubble_sort
    tmp = self.dup
    res = []
    res.push tmp.bubbling until tmp.empty?
    res
  end

  def bubbling
    (length-1).times do |i|
      self[i], self[i+1] = self[i+1], self[i] if self[i] < self[i+1]
    end
    delete_at(-1)
  end

  def quick_sort
    return self if length <= 1
    base = pop
    smaller, bigger = partition { |e| e < base }
    push base
    smaller.quick_sort + [base] + bigger.quick_sort
  end

  def merge_sort
    tmp = self.dup
    return tmp if tmp.length <= 1
    a, b = self.half.map { |e| e.merge_sort }
    merge(a, b)
  end

  def half
    mid = length/2
    return slice(0...mid), slice(mid..-1)
  end
  
  def merge(a, b)
    res = []
    until a.empty? && b.empty?
      res <<
        case
        when a.empty? then b.shift
        when b.empty? then a.shift
        when a.first < b.first then a.shift
        else b.shift
        end
    end
    res
  end
end

@@result = {}

class TestSorts < Test::Unit::TestCase
  def setup
    num = 1000
    @list = []
    num.times { @list << rand(num)  }
  end

  def time(name)
    t = Time.now
    res = yield
    @@result[name] = Time.now - t
    res
  end

  def test_insert_sort
    assert_equal(@list.sort, time(:Insert){ @list.insert_sort })
  end
  
  def test_select_sort
    assert_equal(@list.sort, time(:Select){ @list.select_sort })
  end
  
  def test_bubble_sort
    assert_equal(@list.sort, time(:Bubble){ @list.bubble_sort })
  end
  
  def test_quick_sort
    assert_equal(@list.sort, time(:Quick){ @list.quick_sort })
  end
  
  def test_merge_sort
    assert_equal(@list.sort, time(:Merge){ @list.merge_sort })
  end

  def test_sort
    assert_equal(@list.sort, time(:Sort){ @list.sort })
  end

  def test_keep_self
    original = @list.dup
    %w(insert select bubble quick merge).each do |name|
      @list.send("#{name}_sort")
      assert_equal(original, @list)
    end
  end
end

END{
  END{
    res = @@result.map { |k, v| [k, v, (v/@@result[:Sort]).to_i ] }.sort_by { |e| e[2] }
    res.each { |k, v, n| puts "#{k}\t=>\t#{v} (#{n})" }
  }
}