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