MergeSort in Ruby

Finally got the ball rolling on the 'Introduction to Algorithms' book.. What I figured was that I implement the sorting algorithms in ruby - help me get better at ruby AND algorithms.
I've got to confess.. I'm test-infected so I'm gonna TDD my way out. This series of posts are not going to be in a walkthrough style of narration.. I'm just going to post complete samples. The order of methods indicate how the code was built up.. (the first method is the 'oldest'.

Here's merge_sort_test.rb [The Test Fixture]
--
require 'test/unit'
require 'merge_sort'
class TestMergeSort < Test::Unit::TestCase
def test_partition_array_with_even_number_of_elements
left, right = MergeSort.partition_array [11, 5, 9, 15]
assert_equal [11, 5], left
assert_equal [9, 15], right
end
def test_partition_array_with_odd_number_of_elements
left, right = MergeSort.partition_array [11, 5, 45, 9, 15]
assert_equal [11, 5], left
assert_equal [45, 9, 15], right
end

def test_merge_arrays
assert_equal( [10,20,30,40],
MergeSort.merge_arrays( [10,30], [20,40] ) )

assert_equal( [1, 3, 5, 9],
MergeSort.merge_arrays( [1, 5, 9], [3] ) )
assert_equal( [1, 3, 5, 9],
MergeSort.merge_arrays( [3], [1,5,9] ) )
end

def test_sort
assert_equal [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
MergeSort.sort([ 8, 3, 4, 0, 9, 1, 2, 7, 6, 5])
end
end


--
merge_sort.rb [The Implementation]
--
class MergeSort 
def self.partition_array( input_array)
mid_index = (input_array.length / 2) - 1
[input_array[0..mid_index], input_array[(mid_index+1)..(input_array.length-1)]]
end

def self.merge_arrays(array1, array2)
merged_array = []

until (array1.empty? || array2.empty?) do
if (array1[0] < array2[0])
merged_array << array1.shift
else
merged_array << array2.shift
end
end

merged_array + array1 + array2
end

def self.sort( input_array )
return input_array if (input_array.length < 2)

left, right = self.partition_array input_array
sortedLeft = self.sort left
sortedRight = self.sort right
y = self.merge_arrays( sortedLeft, sortedRight )
end
end



--
A command line 'runner'/'main' function
--
# Console runner / main
if !ARGV[0].nil?
input = []
ARGV.each{|x| input << x.to_i}
print MergeSort.sort(input).inspect
end


--
>ruby merge_sort.rb 90, 100, 40, 10, 45
[10, 40, 45, 90, 100]

And we're done! IMHO The Ruby Array class really shines here w.r.t. readability.

No comments:

Post a Comment