3 Essential Algorithm Examples You Should Know

There are certain algorithms that come up again and again. In this tutorial, we will explore three of the most common: searching, sorting, and adding to/removing from a linked list. The ideas surrounding these algorithm examples permeate throughout many other algorithms . Understanding these three examples, will help us build a solid foundation so we can tackle future algorithm problems with confidence!

Algorithm Examples, #1: Binary Search

Binary search is an essential search algorithm that takes in a sorted array and returns the index of the value we are searching for. We do this with the following steps:

1. Find the midpoint of the sorted array.
2. Compare the midpoint to the value of interest.
3. If the midpoint is larger than the value, perform binary search on right half of the array.
4. If the midpoint is smaller than the value, perform binary search on left half of the array.
5. Repeat these steps until the midpoint value is equal to the value of interest or we know the value is not in the array.

From the steps above, it is clear that our solution can be recursive. We will pass in a smaller array to our method on each iteration until our array only contains the value we are interested in. The tricky parts are indexing our array properly and keeping track of our index offset on each iteration so that we can return the index of our value from the original array. See below for our version of the binary search algorithm.

def binary_search(arr, value, offset=0)
  mid =  (arr.length) / 2
  
  if value < arr[mid] binary_search(arr[0...mid], value, offset) elsif value > arr[mid]
     binary_search(arr[(mid + 1)..-1], value, offset + mid + 1)
  
  else
     return offset + mid
  end

end

Binary search has a time complexity of O(logn). We know this because if we double the size of our input array, we only need one more iteration of our algorithm to arrive at our final answer. This is why binary search is such a significant algorithm in computer science.

Algorithm Examples, #2: Merge Sort

Merge sort,uses a similar “divide and conquer” methodology to efficiently sort arrays. See the following steps for how merge sort is implemented.

1. Return if array is only one element long, because it is already sorted.
2. Divide array into two halves until it cannot be divided anymore.

1. Merge smaller arrays in sorted order until we have our original sorted array.

To implement merge sort, we will define two methods. One will take care of the splitting up of the array and the other will take care of merging two unsorted arrays back into a single sorted array. We call the dividing-up-method (merge_sort) recursively until our array is only one element long. We then merge them back together and finally return our sorted array. See below:

def merge_sort(array)
  return array if array.length == 1

  mid_point = array.length / 2
  left = array[0...mid_point]
  right = array[mid_point..-1]

  merge(merge_sort(left), merge_sort(right))

end

def merge(left, right)
    merged_arr = []

    until left.empty? && right.empty?
      if left.length == 0
        merged_arr << right.shift
      elsif right.length == 0
        merged_arr << left.shift
      elsif left[0] <= right[0]
        merged_arr << left.shift
      elsif right[0] <= left[0]
        merged_arr << right.shift
      end
    end
    merged_arr
end

Merge Sort has a time complexity of O(nlogn), which is the best possible time complexity for a sorting algorithm. By dividing and conquering, we dramatically improve the efficiency of sorting, which is already a computationally expensive process.

Algorithm Examples, #3: Adding and Removing From a Linked List

The linked list is a fundamental computer science data structure, that is most useful for it’s constant time insertion and deletion. By using nodes and pointers, we can perform some processes much more efficiently than if we were to use an array. See below for a schematic:

A linked list is made up of nodes which each have a piece of data and a pointer to the next node. We represent this in Ruby by creating a struct, Node, with two arguments, :data and :next_node. Now, we just have to define two methods, insert_node and delete_node that take in a head node and a location of where to insert/delete. The insert_node method has an additional argument, node, which is the node struct we want to insert. We then loop until we find the location we would like to insert into or delete from. When we arrive at our desired location, and rearrange the pointers to reflect our insertion/deletion.

Node = Struct.new(:data, :next_node)

def insert_node(head, node, location)
  current_node = head
  current_location = 0

  until current_location == location
    previous_node = current_node
    current_node = current_node.next_node
    current_location += 1
  end

  if previous_node
    previous_node.next_node = node
    node.next_node = current_node
  else
    node.next_node = current_node
  end

  head

end

def delete_node(head, location)
  current_node = head
  current_location = 0

  until current_location == location
    previous_node = current_node
    current_node = current_node.next_node
    current_location += 1
  end

  if previous_node
    previous_node.next_node = current_node.next_node
  else
    head = current_node.next_node
  end

  head
end

With a linked list, we can delete items from the middle of a collection without having to shift over the rest of the data structure in memory, like we would have to if we were using an array. By choosing the best data structure for our needs, we can reach optimal efficiency!

What’s Next?

These three algorithm examples are just the surface of fundamental algorithms we should know to both create efficient programs and succeed at technical interviews. Here are some more algorithms we can explore on our own to further our knowledge.

1. Quicksort
2. Traverse a binary search tree
3. Minimum spanning tree
4. Heapsort
5. Reverse a string in place

These are difficult concepts to grasp, so we just have to keep practicing and understand more algorithm examples!

Other tutorials you might be interested to read:

• Introduction to Greedy Algorithms
• Two Algorithms for Solving Vigenere Cipher in Ruby
• Implementing Google’s Two-Step Authentication to Your App
• 6 Ruby Best Practices Beginners Should Know

Author’s Bio

Hannah Squier is a self-taught software developer, with a background in GIS and civil engineering. As a UC Berkeley Engineering graduate and early startup employee, she has navigated many complex challenges with her technical know-how and perseverance. While preparing for her next adventure to become a full time software engineer, she writes tutorials to give back to the developer community.  When she’s not coding, Hannah plays frisbee and thinks about how to make cities better places to live in. Get in touch at hannahsquier@gmail.com.