Created
October 12, 2010 13:19
-
-
Save melborne/622151 to your computer and use it in GitHub Desktop.
Sort Algorithms in Ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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