Read it, Learn it, Build it: Sorting Algorithms in Ruby

For the past few weeks, I’ve been constantly distracted by shiny new things: Angular2 photo gallery! Rails contact form! Python price scraping! I’ve been so distracted that I haven’t been very good with following up in my intentions to improve my understanding of algorithms. This past week, I finally sat down and focused on the sorting algorithms. I’m a big fan of Youtube videos explaining the concepts to me, but of course, you don’t really know how something works until you build it.

So here we go!

Rick & Morty on AdultSwim — seriously, watch it

Bubble Sort

The idea behind bubble sort is that the larger elements will “bubble” towards the end and the smaller elements will “bubble” towards the beginning until all elements are in their correct location. This occurs through repeated swapping of adjacent elements if they are in the wrong order. This algorithm starts at the beginning of the array, compares each element with the element immediately to the right of it, and makes a swap if the elements are out of order with each other. By the end of each pass through the array, it’s never a guarantee that all the items are sorted or all items are not sorted because the algorithm only compares pairs of items at a time. How will we ever know if the items in the array are sorted??

Here we create a variable swap that is a flag to indicate whether or not a swap occurred during a given pass of the array. If the swap returns false at the end of the pass, that means no swaps occurred because everything was in order, and therefore, the array is sorted.

Ruby implementation:

  1. bubble_sort takes in a single array parameter.
  2. If the array size is 1 or 0, return the array; by default, an empty array or array with one element is sorted.
  3. Create the swap variable and set it to true by default.
  4. Create a while loop that will run as long as swap is true.
  5. Set swap = false since immediately after the beginning of your loop, there have been no swaps.
  6. In the loop, iterate through each element of the array and check if element x is greater than the element next to it x + 1. If so, swap the value of x with value of x+1 and set value of swap to true since we did make a swap.
  7. The loop repeats until every item is in order and the value of swap remains at false. The loop will terminate and the array will be returned.

Insertion Sort

The best analogy for insertion sort is to imagine you have a hand of cards, and you need to put them in order from smallest to greatest. The hand is originally all random, and you hold at least one card constant while you move the other cards around it to sort everything into order. The element that you’re considering (let’s call it a key) could be moved one spot or over multiple spots.

Ruby implementation:

  1. First, we iterate through all elements of the array with (array.length).times do. j represents the index of the item in the array.
  2. Then we set the if/else checks to run only if j > 0 (element is not the first item, which has index 0).
  3. The if/else checks compares the previous element with the current element; if previous element is larger than current element, swap previous with current.
  4. If previous element is not larger than current element, the if/else terminates.
  5. The j counter is decremented by 1.

Selection Sort

Selection sort constantly looks for the minimum element and adds it to the front of a separate array. With a given array, usually two subarrays need to be maintained: one that holds unsorted elements and one that holds sorted elements. In Ruby, you can get away with just manipulating the input array.

Assume the first element of the array is the minimum index, and compare each subsequent element to the min_index element, setting a new min_index element whenever an array element is less than value of the element at min_index.

Ruby Implementation:

  1. Set n equal to array.length — 1: this represents how many times you need to do the comparisons.
  2. Set a min_index value equal to your initial i index (should be the first element in array).
  3. Create a second (nested) loop starting at the second element until n using variable j.
  4. Compare the value of element at index j with value of element of min_index. If value of element at index j is less than value of element of min_index, index j becomes the new min_index. Set min_index = j if this is the case. Exit the inner loop.
  5. If value of new min_index is not equal to value of element at i then swap value of element at i index with value of element at min_index.
  6. Lastly, return the manipulated array.

Merge Sort

Everyone’s favorite divide-and-conquer algorithm, merge sort makes a lot of intuitive sense, but I found it somewhat tricky to code. Best analogy here is to imagine searching through a telephone book for someone named “Smith”. Imagine splitting open the book down the middle and arriving at the “M” section. Does “S” come before or after “M?” Since it comes after, you can now ignore the entire first half of the book, and focus your search on the second half. Open to a random spot in this second half and you arrive at “R”. Is “S” before or after “R”? It comes after, so now you can ignore all sections “M” through “R”, and continue your search. The goal is to divide a problem into smaller chunks until the solution can be found.

The algorithm contains two main methods:

  • a merge_sort method that makes recursive calls upon itself
  • a merge method that will merge the subarrays in a sorted manner

But first, recursion!

To understand recursion, you must understand recursion.

Merriam Webster defines recursion as:

a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first

It is a process in which a function will call itself directly or indirectly, usually on a smaller chunk of the original data set with each call. The recursive function will continue to call itself until it reaches a stopping point that is usually defined in the function. Otherwise, you could get caught in an infinite loop. And nobody has time for that!

First, (and as I write this, I realize this is applicable to all of the sorting algorithms), if you have an array that is empty or has only one element, by default that array is sorted. We will want to check for that condition to prevent doing any unnecessary work.

Ruby Implementation — Merge Sort function

  1. Check the input array length. If it is 0 or 1, return the array (already sorted!)
  2. If array length is greater than 1, then we want to define a mid-point, picked by choosing array.length / 2 and call a floor method so the number always rounds down.
  3. Use the midpoint to divide the array into halves, a left and right. I set my left array to start with first element and end at element mid — 1. My right array starts at mid and ends at the last element. (Note: Ruby ranges .. are inclusive of the last element, whereas ... are exclusive of last element).
  4. Note that not only do I set left and right subarrays equal to the lengths above, but they’re set to the merge_sort version of those subarrays. That means that merge_sort will be called upon these subarrays, which means picking a new midpoint, dividing the subarray into halves, and set left and right subarrays that will call merge_sort again.
  5. Lastly, I have a call to the merge method to combine the left and right subarrays into one array.

Ruby Implementation — Merge

  1. Once the subarrays are broken down into the smallest pieces possible, now it’s time to sort and merge them together.
  2. If one of the two subarrays are empty, by default only information in the non-empty subarray is returned.
  3. If the subarrays are not empty, then we compare the value of each element in the first index position. If the first element of left array is smaller than the first element of right array, then we build the sorted subarray beginning with the first element of left array + the value of a recursive merge function call which takes left[1..left.length],right as the input parameters. It starts with the second element at index 1 since the first element has already been “sorted”.
  4. If first element of left array is larger than first element of right array, the opposite occurs. We indicate the first element of the right array is “sorted” and call merge on what remains: left, right[1..right.length].

Essentially, you will take an array, break it down until subarrays of single elements exist, and then combine each subarray with its left/right counterpart until the final array of original length is returned. I visualized this in the shape of a diamond, where the top and bottom points are the final array, and center of the diamond indicates the numerous amount of subarrays that need to be dealt with.

Quick Sort

This one was probably the second-to-hardest sort to wrap my head around. The algorithm picks a pivot, a random element in the array, and sorts the elements around it based on whether or not an element is greater than or less than a pivot. After the first pass when every value less than the pivot is on the left hand side and every value greater than the pivot is on the right hand side, we break into two subarrays and apply quick sort to each half (pick a new pivot, compare elements, break into two subarrays).

Ruby Implementation:

  1. First, our checks to see if array.length <= 1.
  2. Pick a pivot at random. Ruby’s delete_at method will delete the item at the specified index, which in this case would be a rand index in the range of array.length. We’re saving the value of that item to pivot.
  3. Create a new left and right subarray.
  4. Loop through every element in the array and compare it to the pivot. If the value is less than pivot, add element to the left subarray. If value is greater than pivot, add element to the right subarray.

Heap Sort

Lastly, I looked into heap sort. This sorting relies on the use of a specific tree data structure — the heap, and most specifically, a max heap. I covered it briefly in my flash post on data structures, but I have to recap it anyway. A tree has a root node and many children, grand-children, great-grand-children etc nodes below it. A heap is a type of tree in that satisfies the heap property: if node P is parent of child node C, then the value of item at parent node P is greater than value of child node C. A max heap is a specific type of heap where the value of parent node at any given level of subtree is greater than value of child nodes. And it is the max heap structure that we use for heap sort. See, by the rules of max heap, since the root node of the heap is ALWAYS the largest value in the tree, we can build a sorted array by repeatedly removing the root node, push it to our new array, and heapify the max heap again so that the new, largest value node is at the root.

This algorithm made intuitive sense to me, but my biggest challenge was in coding it, especially implementing it in Ruby. I needed methods to do a couple of things: to build a heap with a given array, to sort the root node, and then reshuffle the remaining elements back into a heap.

Ruby Implementation:

  1. In def heap_sort, we first build a max heap (lines 5–7).
  2. Then, we call a loop: while the array length is greater than 1, swap root element with the last element, reduce the length by 1 (since we have sorted one item), and re-build the heap so that it satisfies the max-heap condition.
  3. At the end, we remake the array into its original size and revert the root back to index [0].
  4. The def heapify method will sift the elements until they’re in their rightful place.
  5. parent indicates where to start sifting and limit tells how far down the heap to sift.
  6. Set parent node as the root. While the child index is less than or equal to the limit (indicates that root has at least one child), we increment child by 1 to get it’s sibling IF the child is less than limit and the value of child is smaller than value of it’s sibling. The loop terminates if value of root is greater than value of child (since root must always be greater than children in a max heap). Otherwise, swap the value of parent and child, and after the loop, we set the array[parent] equal to the stored root value.

After getting the implementation to work, there were still two lines that bothered me: a = [nil] + array and a.drop(1). They’re both related and necessary for the above code to work, but the WHY? kept gnawing at me. I was able to sit down with a mentor to review the code and we worked out what those lines were doing as well as why I didn’t need them. Here’s the modified implementation:

The two lines in question were related to an out-of-bounds issue on my array. Based on the create_max_heap formula, child could end up being out of bounds; in an array with 10 items, it’s possible to havechild = 10 but the actual index of child is 9. Adding the [nil] to the array adds an extra element at index 0 so that the rest of the indices line up with how they’re being calculated in create_max_heap. The solution was to adjust n from array.length to array.length — 1 , adjust downto(1) to downto(0), set swaps to be a[0], a[n]= a[n],a[0], set loop to run while n > 0, and pass 0 as the parent element in create_max_heap.

Next steps would be to apply the various sorting algorithms to different data structures and see what that might look like. At some point, I’ll also look into the various common applications of the above algorithms and see how they apply to real life!

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.