Introduction to Algorithms with Ruby

There are many reasons why you should learn about algorithms. They are a fundamental part of computer science and they play a key role in modern technological innovation. Besides that, learning basic algorithms is a good way to develop your problem solving skills and to better understand the software and programming languages you work with on a daily basis.

So let’s say you’re a self taught Ruby developer and you want to improve your computer science fundamentals by learning some algorithms. Where do you start? The amount of theory available can be quite overwhelming. This guide is my attempt to narrow it down to a short introduction that you can start with right now, and you don’t even have to learn C or Java first.

Approach

So what is an algorithm anyway?

An algorithm is a plan, a logical step-by-step process for solving a problem.

By this definition, any method/function can be an algorithm. However, algorithms are usually a bit more complex than your average function and often involve multiple steps to solve a problem. Anyway, the best way to learn what an algorithm is, is to implement one yourself.

Before doing so, we need to know about the required steps involved in our approach to solving problems.

  1. First, define a high level description of the problem, the input and desired output.
  2. Second, break down the solution with pseudocode, a form of structured English that resembles a programming language.
  3. Convert your pseudocode to a working implementation in Ruby.

After implementing your algorithm, try to keep improving it. Can it be done more efficiently? Can you refactor or rename things?

Selection sort

In this guide, we take two (relatively) simple algorithms in two of the most fundamental challenges in computer science: sorting and searching. The algorithms we use (selection sort and binary search) are not the fastest or most efficient, but they are a good starting point if you’ve never worked with algorithms before.

Let’s get started by following the steps in the process:

1. Problem description, input and output.

There are two ways to do this. One is to find a high level description of the selection sort problem, and implement the code yourself. However, if you don’t have any experience with algorithms, I recommend watching a tutorial that explains the algorithm step by step. Let’s head over to the Mycodeschool Youtube channel for a great explanation of selection sort.

IMAGE ALT TEXT HERE

Based on the explanation in the video, we can define the following problem description.

Given an array of integers, the selection sort algorithm sorts by iterating over each number in the array and then swapping it with the sorted position of the element. We keep track of the integers that are sorted by using a minimum element. Our algorithm should return a sorted array.

2. Breaking down the problem with pseudocode

I recommend converting the pseudo code from the video to your own pseudocode. Try to understand each of the steps and add comments for extra clarification.

#function with the array and the number of elements as arguments
 selection sort(a, n)
  #main loop iterating over the array (with exception of the last element)
   for i to n - 2
     #storing the minimum element starting with the the first element
     index_minimum = i

     #scanning the array and comparing elements with the current minimum
     for j i + 1 to n - 1
      #if the element is less than current element, update min value
       if a[j] < a[index_minimum]
        index_minimum = j 
    
    #swapping the elements
    temp = a[i]
    a[i] = a[index_minimum]
    a[index_minimum] = temp

3. Ruby implementation

Now we can convert our language independent pseudocode to Ruby. One thing that stands out in this example, is the use of for loops. In general, using for loops is discouraged in Ruby. So instead of using a for loop, we can use each to iterate over a range, as you can see in the example below.

#require "byebug"
 
 def selection_sort(a, n)
  (0..n - 2).each do |i|
    i_min = i
    (i + 1..n - 1).each do |j|
      if a[j] < a[i_min]
        i_min = j
      end
    end

    temp = a[i]
    a[i] = a[i_min]
    a[i_min] = temp
    #byebug
  end
  a
end

a = [2,7,4,1,5,3]
selection_sort(a, a.size)

*extra: Use Byebug to halt the loop and check the state of your array (a). Use ‘continue’ to run the next iteration. Drop your byebug statement after the swapping of the elements.

So we’ve learned our first sorting algorithm. Up next is one of the most well known and fundamental search algorithms: Binary Search

1. Problem description, input and output.

Once again, we head over to Mycodeschool on Youtube. Try to understand every step, and pause the video if you need to.

IMAGE ALT TEXT HERE

Based on the explanation, we can define the problem:

Given a sorted array ( a precondition for Binary search), find value x by reducing the search space by half with each comparison. To do this, we need to keep track of our search space. The algorithm should return the index if the value is found, or “not found”.

2. Breaking down the problem with pseudocode

#search function with a sorted array, size of the array, and value to find
binary_search(array, n, x)
  # set the search space to the entire array
  index_start = 0
  index_end = n - 1
  # loop until we can't divide the array any further
   while index_start <= index_end
    # find the middle element in our search space
     middle = ( index_start + index_end ) / 2
     # 3 possible cases in searching
     # x matches the middle element
     if array[middle] == x
       return middle
    #x is less then middle element - > reduce search space / 2
     elsif x < array[middle]
      index_end = middle - 1
     else 
     # x is larger than middle element -> reduce search space / 2
       index_start = middle + 1
  # return not found if our loop is completed and we've found no matching element
  return -1 (not found)

3. Ruby implementation

If your pseudocode is understandable, converting it to Ruby should not be difficult. See the example implementation below. A note here is that return statements are not necessary in Ruby, but I’ve left them in for some extra readability.

 def binary_search(a, n, x)
  index_start = 0
  index_end = n - 1

  while index_start <= index_end do
    index_middle = (index_start + index_end) / 2
    if a[index_middle] == x
      return index_middle
    elsif x < a[index_middle]
      index_end = index_middle - 1
    else
      index_start = index_middle + 1
    end
  end
  return "not found"
end

a = [1, 2, 3, 4, 5, 7]
puts binary_search(a, a.size, 3)

Bubble sort

As an exercise, read a high level description of Bubble Sort and try to implement the algorithm yourself, before watching the step by step explanation. Remember to use the steps in the approach to solving a problem.

What else do you need to know?

Before you continue, getting a basic understanding of the following topics is recommended.

Asymptotic notation

When working with algorithms, efficiency is everything. If you’ve watched the video, you’ve heard about a “time complexity analysis” and something called O(n2). This is called “Asymptotic notation” and “Big O notation”. In a nutshell, asymptotic notation is a method to describe your algorithms performance, based on the amount of data it’s processing. Check out the resources below to learn more;

Data structures

Essential for not just algorithms but software development in general, is the concept of data structures. Data structures are objects that organize data with various operations that can be used to retrieve or manipulate the data stored within them. We’ve used a concrete implementation of a data structure (arrays) in our algorithm examples.

Data structures is a large topic, but for now, what you need to know is that the type of data structure and the way you retrieve and/or manipulate data directly affects your algorithms performance. It’s recommended to get a basic understanding of different common data structures, their performance in certain situations and the differences between them.

Examples of common data structures are stacks, queues, linked list, tree and graph. Mycodeschool has a great series on data structures that you can watch here:


That’s it for this very small introduction to algorithms! Hopefully, this provides a starting point for further exploration and practice. If you have any questions or feedback, let me know in the comments.

Sources