Sorting algorithms in Ruby, Part 1

For fun, I decided to implement some classic sorting algorithms in an object oriented language. In this case Ruby.

Later I plan to implement some sorting algorithms in a functional language to contrast the differences.

For now, here are the algorithms I chose the implement.

Bubble sort
Selection sort
Insertion sort
Merge sort

I implemented those by reading the textual descriptions of the algorithms on Wikipedia and trying to refrain from looking at actual source code or pseudo code.

To test the algorithms I wrote some simple test cases.

require 'test/unit'
require './bubble_sort.rb'
require './selection_sort.rb'
require './insertion_sort.rb'
require './merge_sort.rb'

class SearchTest < Test::Unit::TestCase
	@@unsorted = [5, 2, 3, 8, 1, 3, 12, 10, 11, 6]
	@@sorted = @@unsorted.sort 
	
	def test_bubble_sort		
		bubble_sort = BubbleSort.new
		result = bubble_sort.sort(@@unsorted)
		
		assert_equal @@sorted, result
	end
	
	def test_selection_sort
		selection_sort = SelectionSort.new
		result = selection_sort.sort(@@unsorted)
		
		assert_equal @@sorted, result
	end
	
	def test_insertion_sort_out_of_place
		insertion_sort = InsertionSort.new
		result = insertion_sort.sort_out_of_place(@@unsorted)
		
		assert_equal @@sorted, result
	end
	
	def test_insertion_sort_in_place
		insertion_sort = InsertionSort.new
		result = insertion_sort.sort_in_place(@@unsorted)
		
		assert_equal @@sorted, result
	end
	
	def test_merge_sort
		merge_sort = MergeSort.new
		result = merge_sort.sort(@@unsorted.dup)
		
		assert_equal @@sorted, result
	end
	
	# Additional tests on merge sort since it's more complex than the others
	def test_merge_sort_random_arrays
		merge_sort = MergeSort.new
		a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
		
		assert_equal a, merge_sort.sort(a.shuffle)
		assert_equal a, merge_sort.sort(a.shuffle)
		assert_equal a, merge_sort.sort(a.shuffle)
	end
end

In these tests I create an unsorted array which I then sort using Ruby’s built-in sort method. I then run the unsorted array into various objects implementing the algorithms and compare the results with the one sorted by Ruby.

Bubble sort

The first one is bubble sort. It’s fairly inefficient, the complexity is O(n²). If you have done some CS classes in the past you probably went over this one. It iterates over the array, comparing two values at a time and bubbles up the highest values to the end of the array. It continues doing this until it can determine that no more swaps are needed. In other words, that the array is now sorted.

While it can beat some algorithms for nearly sorted arrays, ie: [1, 2, 4, 3, 5, 6], in the real world it’s uses are mostly academic.

class BubbleSort
	def sort(to_sort)
		sorted = false

		until sorted
			sorted = true

			for index in 0..(to_sort.length - 2)
				if to_sort[index] > to_sort[index + 1]
					sorted = false
					to_sort[index], to_sort[index + 1] = to_sort[index + 1], to_sort[index]
				end
			end
		end

		return to_sort
	end
end

There are ways to optimize bubble sort. Rather than looking into common ways to optimize Bubble sort, I will take this time to look into more algorithms.

Selection sort

Selection sort is another inefficient but simple sort. It’s complexity is again O(n²), because of the nested loop.

It’s an in-place sort, meaning that it uses a small constant amount of data to perform it’s sort. In-place is also frequently taken to mean that it works on the data set at hand, by swapping the existing values.

Selection sort works by dividing the array in two; the sorted array at the beginning and the unsorted array at the end. Initially the whole array is unsorted.

The algorithm iterates over the array finding the smallest element. It then swaps this element to put it at the loop’s current index. What this does is add it to the end of sorted elements.

I will illustrate this with a sample array. [3, 6, 1, 2]
The sorted and unsorted values will be divided with a | symbol.

Initial value:
[ | 3, 6, 1, 2]

First pass:
[1 | 6, 3, 2]

Second pass:
[1, 2 | 3, 6]

Third pass:
[1, 2, 3, 6]

As you can see in this example, there is no need to do a fourth pass. When we are left with a single element, it is by definition already sorted.

class SelectionSort
	def sort(to_sort)
		for index in 0..(to_sort.length - 2)
			# select the first element as the temporary minimum
			index_of_minimum = index

			# iterate over all other elements to find the minimum
			for inner_index in index..(to_sort.length - 1)
				if to_sort[inner_index] < to_sort[index_of_minimum]
					index_of_minimum = inner_index
				end
			end

			if index_of_minimum != index
				to_sort[index], to_sort[index_of_minimum] = to_sort[index_of_minimum], to_sort[index]
			end
		end

		return to_sort
	end
end

Insertion sort

For Insertion sort, I read a description stating that the algorithm works by going through the elements to be sorted and inserting them in their correct order in a new sorted array. This is an in-place algorithm. An even easier way to write it, would be to use an out of place algorithm and create another array like this:

class InsertionSort
	def sort_out_of_place(to_sort)
		sorted = []
		
		to_sort.each do |element| 
			for index in 0..(to_sort.length - 1)
				sorted.insert(index, element) if to_sort[index] > element
			end
		end		
		
		return to_sort	 
	end
end

Wow, that one was easy. But now let’s try the slightly harder in-place version. This version works on the array to be sorted rather than create a new array.

def sort_in_place(to_sort)
		# index starts at one, we can skip the first element, since we would
		# otherwise take it and place it in the first position, which it already is
		for index in 1..(to_sort.length - 1)
			for inner_index in 0..(index - 1)
				if to_sort[inner_index] >= to_sort[index]
					to_sort.insert(inner_index, to_sort[index])
					to_sort.delete_at(index + 1)
				end
			end
		end
		
		return to_sort
	end

Ok, so it’s not that much more complicated. That’s because I used Ruby’s insert and delete_at. Normally in my inner loop I would have had to shift (move) manually all the elements in-place to put my new element to be sorted in the right position thus repositioning many elements.

What this means is that my implementation is really only truly in-place if Ruby’s insert and delete_at are implemented in-place themselves. The logic of the algorithm can be considered in-place if we consider the two methods as abstractions.

Either way, this is a more faithful implementation of the original algorithm than the first out of place version. Doing it in-place uses less memory than the out of place version but is slightly harder to code and understand.

As for the complexity it’s a O(n²) algorithm, but it is considered more efficient in practice than Selection sort and Bubble sort.

Let’s move on to a more efficient algorithm.

Merge sort

Because recursion kicks ass!

Now we are getting at more interesting and more efficient algorithms. Merge sort is an O (n log n) algorithm. This is a lot better than the previous algorithms. It’s also the first to use recursion thus using a divide and conquer approach.

I have commented the code, and will let these comments and the source code do most of the talking.

lass MergeSort
	def sort(to_sort)
		# if the array is of length 0 or 1, consider it is already sorted
		if to_sort.length <= 1 
			then return to_sort 
		end
		
		# otherwise split the remaining elements in two
		# I had to look this line on the web (source refactormycode.com)
		second_array = to_sort.slice!((to_sort.length / 2.0).round..to_sort.length)
				
		# recursive method call on both arrays
		first_sorted_array = sort(to_sort)
		second_sorted_array = sort(second_array)
		
		# merge the two sorted arrays together
		return merge(first_sorted_array, second_sorted_array)
	end
	
private
	def merge(first_array, second_array)
		# if either array is empty consider the other already sorted
		return second_array if first_array.empty?
		return first_array if second_array.empty?
		
		# remove the smallest element out of the two arrays
		if first_array.first <= second_array.first 
			element = first_array.shift
		else
			element = second_array.shift
		end		
	
		# recursive call to construct the merged array	
		return [element] + merge(first_array, second_array)
	end
end

To implement Merge sort, you also need to implement a merge function. This function will pick values from two arrays and construct a merged sorted array. The two arrays used for input are considered already sorted. The job of the merge function is then to look at the first element of each of these arrays and find the smallest.

ie:

[1, 4, 7, 9] and [2, 5, 6]
[]

In this case the merge function would look at 1 and 2. Select 1 as the smallest value and remove it from the first array. The value would then be used as the first value of the new merged array.

[4, 7, 9] and [2, 5, 6]
[1]

The process then repeats itself until there are no more elements in either arrays.

For your merge function you can use an iterative approach. In such an approach you loop, taking elements from the two arrays to be merged and placing them in a merged array, until you have no more elements left to take from the original arrays.

Since Merge sort is a recursive algorithm, I also went with a recursive merge function.

When I write a recursive function, I always start by defining the condition(s) that will end the recursion and then consider what I need to do to get to this condition.

In this case, we will end the recursion when one or our arrays to be merged is empty. If this is the case, we can return the other array as there are still values in it to be merged.

If we are not facing an empty array, we simply need to look at the first value from each array, remove it and return it along with a recursive call to merge.

This merge function required more thinking than the actual sort function which just keeps splitting the array in two, calling sort recursively on both of the new arrays.

Until next time…

This is it for part 1. Stay tuned for part 2 where I will look into more sorting algorithms in Ruby, more specifically heapsort and quicksort.

Sorting algorithms in Ruby, interlude
Sorting algorithms in Ruby, Part 2
Sorting algorithms in Ruby, Part 3