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 stepbystep 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.
 First, define a high level description of the problem, the input and desired output.
 Second, break down the solution with pseudocode, a form of structured English that resembles a programming language.
 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.
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.
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.
*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.
Binary search
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.
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
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.
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

Examples of common algorithms implemented in Ruby: Google Summer of code, Ruby Algorithms

A huge list of CS resources, useful if you know what your looking for