Skip to content

Instantly share code, notes, and snippets.

@melborne

melborne/sorts.rb

Created Oct 12, 2010
Embed
What would you like to do?
Sort Algorithms in Ruby
#!/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})" }
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.