Ruby, which is progressively gaining popularity in the industry, has struck an interest with me, and I've decided to take up the task of learning the language. Although I was first introduced to Ruby back in 2002, I never took the time to really get to know it.

Fast forward 6yrs later, and I've decided to get serious about it, and what better way to learn than to get in there and code up some common algorithms. As I venture on this journey, I will document my experience in efforts to help out others who are learning as well.

For this first example, I've coded up the simple "Insertion Sort" algorithm. Please note that in my attempts to "rubify" the algorithm, it is highly likely I may not have written it efficiently.

def insertion_sort (list)
   list.each_with_index do |element, index|
      index.downto(0) do |j|
         if (j > 0 && element < list[j-1]) then
            list[j] = list[j-1]
         else
            list[j] = element
            break
         end
      end
   end
end

Insertion sort operates on the basis that elements are sorted progressively as the code scans the list, and therefore after each scan S, elements 0 through S-1 are assumed to be in order, and element S is moved towards the left until it is in order.

Code Walkthrough
The following lines uses the standard list iterator API to obtain both the element and it's index, starting at the beginning of the list.

list.each_with_index do |element, index|

The inner loop uses the "downto" construct to start at the current index (from the outer loop), and counts backward to "0". Note that "downto" does not alter the value of "index". This loop does the work of comparing and swaping the current element with it's predecessors, and will appropriately shift "greater" ones up the list.

index.downto(0) do |j|

The following code segment defines the comparison logic in order to shift the element down the list, by moving all "greater" elements up the list. Once an appropriate location has been determined, the current element is inserted back into the list.

if (j > 0 && element < list[j-1]) then
   list[j] = list[j-1]
else
   list[j] = element
   break
end

One very important point to note is that array boundaries are somewhat loose in Ruby, and therefore an index of "-1" is considered legitimate and will not produce an array/list access violation -- it would point to the last element in the list. Therefore, in the core logic presented above, we account for that by detecting when "j" is no longer greater than "0" in our conditional statement. Regardless, in order to properly implement "insertion sort", strict boundaries are needed.


Additionally, due to Ruby's OO nature, the code presented above will work with any list of classes that support the "<" comparison operator. With that being said, Ruby also makes it possible to have lists that contain a heterogeneous set of classes since there is a lack of type-safety -- this can be both an advantage or disadvantage depending on how you intend to use this algorithm. If you're using a mixed set of classes, you would have to ensure that there is some logical ordering defined within your classes to satisfy the comparison methods.


I hope this tutorial has been helpful!