Sorting algorithms in Ruby, interlude

Hello.

The next installment of Sorting algorithms in Ruby, will come out tomorrow night.

Before it does I wanted to use a separate post to present something that will be used in tomorrow’s post. I am doing it here because tomorrow’s post is already very long as it is.

Reusing test logic

Since the next two algorithms, Heap sort and Quicksort are more complex than my previous sorts, I wanted to make sure I had a robust testing suite.

When you consider the test cases for a given sorting algorithm, you can see that they can apply to any sorting algorithms. For this reason, I moved the actual testing code in a separate class named SortTest, which I will be able to reuse for any algorithms in the following installments.

Here it is:

class SortTest 
	def initialize(sort_algorithm)
		@sort_algorithm = sort_algorithm
	end
	
	def test_empty_array
		empty_array = []
		
		return test(empty_array, empty_array)		
	end
	
	def test_array_with_one_element
		array_with_one_element = [1]
		
		return test(array_with_one_element, array_with_one_element.dup)
	end
	
	def test_ordered_array
		ordered_array = [1, 2, 4, 5, 6, 7]
				
		return test(ordered_array, ordered_array.dup)
	end
	
	def test_array_with_even_number_of_elements
		array_with_even_number_of_elements = [10, 23, 43, 45, 8, 2, 4, 9]
		sorted = array_with_even_number_of_elements.sort
		
		return test(array_with_even_number_of_elements, sorted) 
	end
	
	def test_array_with_odd_number_of_elements
		array_with_odd_number_of_elements = [56, 3, 45, 11, 2, 3, 1]
		sorted = array_with_odd_number_of_elements.sort
		
		return test(array_with_odd_number_of_elements, sorted) 
	end
	
	def test_medium_sized_array
		medium_sized_array = [6, 3, 5, 7, 1, 2, 8, 39, 23, 12, 34, 11, 32, 4, 13]
		sorted = medium_sized_array.sort
		
		return test(medium_sized_array, sorted)
	end
	
	def test_reversed_sorted_array
		reversed_sorted_array = [45, 33, 28, 25, 24, 19, 15, 14, 13, 12, 11, 10, 8, 4, 2, 1]
		sorted = reversed_sorted_array.sort
		
		return test(reversed_sorted_array, sorted) 
	end
	
	def test_large_sized_array
		large_sized_array = [5, 2, 3, 8, 1, 3, 12, 10, 11, 6, 17, 13, 4, 9, 18 , 7, 15, 22, 40, 32, 34]
		sorted = large_sized_array.sort
		
		return test(large_sized_array, sorted) 
	end
	
	def test_array_with_repeating_elements
		array_with_repeating_elements = [3, 5, 2, 7, 5, 2, 4, 5, 6, 5]
		sorted = array_with_repeating_elements.sort
		
		return test(array_with_repeating_elements, sorted)
	end
	
private
	def test(initial_array, expected_result)
		actual_result = @sort_algorithm.sort(initial_array)
		result = actual_result == expected_result
		
		if not result
			puts
			puts "Expected result #{expected_result.inspect}"
			puts "Actual result #{actual_result.inspect}"			
		end
		
		return result
	end
end

And here is an example of it’s usage:

require 'test/unit'
require './heap_sort.rb'
require './sort_test.rb'

class HeapSortTest < Test::Unit::TestCase	
	def setup
		heap_sort = HeapSort.new
		@sort_test = SortTest.new(heap_sort)
	end
	
	def test_empty_array
		assert @sort_test.test_empty_array, "Empty array not corectly sorted"
	end
	
	def test_array_with_one_element
		assert @sort_test.test_array_with_one_element, "Array with one element not correctly sorted"
	end
	
	def test_ordered_array
		assert @sort_test.test_ordered_array, "Ordered array not correctly sorted"
	end
	
	def test_array_with_even_number_of_elements
		assert @sort_test.test_array_with_even_number_of_elements, "Array with even number of elements not correctly sorted"
	end
	
	def test_array_with_odd_number_of_elements
		assert @sort_test.test_array_with_odd_number_of_elements, "Array with odd number of elements not correctly sorted"
	end
	
	def test_medium_sized_array
		assert @sort_test.test_medium_sized_array, "Medium sized array not correctly sorted"
	end
	
	def test_reversed_sorted_array
		assert @sort_test.test_reversed_sorted_array, "Reversed sorted array not correctly sorted"
	end
	
	def test_large_size_array
		assert @sort_test.test_large_sized_array, "Large sized array not correctly sorted"
	end
	
	def test_test_array_with_repeating_elements
		assert @sort_test.test_array_with_repeating_elements, "Array with repeating elements not correctly sorted"
	end
end

The reason I added the private test method in SortTest and custom assert messages in my HeapSortTest is because assert alone does not do a good job of reporting test failures.

The assert function will report a failure in this way:

1) Failure:
test_empty_array(HeapSortTest) [heap_sort_test.rb:12]:
false is not true.

Normally, if you use assert_operator or assert_equal you will get a more meaningful message, but with a simple assert the output is a little dry.

With the message parameter and the additional private test method here is the actual result:

Started

Expected result [1, 2, 4, 5, 6, 7]
Actual result [1, 2, 4, 5, 6]
F
Finished in 0.00767 seconds.

1) Failure:
test_ordered_array(QuickSortTest) [quick_sort_out_of_place_test.rb:20]:
Ordered array not correctly sorted.
is not true.

Which is much better. You can clearly see what the problem is with just a quick glance. Ideally all test results should be this easy to read. With such clear messages, our tests will not only show us the errors, they will serve as a first line of debugging information.

2 thoughts on “Sorting algorithms in Ruby, interlude

  1. I’m really learning a lot from your series on sorting algorithms in Ruby and this interlude on testing was awesome as well. I really appreciate you taking the time to put this series together and would encourage you
    to do more of the same as I find your style is very clear, informative and easy to understand. Your really do a great job of explaining everything.

    Again, thank you,
    Mark

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s