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!
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.
bubble_sorttakes in a single array parameter.
- If the array size is 1 or 0, return the array; by default, an empty array or array with one element is sorted.
- Create the
swapvariable and set it to true by default.
- Create a
whileloop that will run as long as
swap = falsesince immediately after the beginning of your loop, there have been no swaps.
- In the loop, iterate through each element of the array and check if element
xis greater than the element next to it
x + 1. If so, swap the value of
xwith value of
x+1and set value of
swapto true since we did make a swap.
- The loop repeats until every item is in order and the value of
false. The loop will terminate and the array will be returned.
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.
- First, we iterate through all elements of the array with
jrepresents the index of the item in the array.
- Then we set the
if/elsechecks to run only if j > 0 (element is not the first item, which has index 0).
if/elsechecks compares the previous element with the current element; if previous element is larger than current element, swap previous with current.
- If previous element is not larger than current element, the
jcounter is decremented by 1.
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
array.length — 1: this represents how many times you need to do the comparisons.
- Set a
min_indexvalue equal to your initial
iindex (should be the first element in array).
- Create a second (nested) loop starting at the second element until
- Compare the value of element at index
jwith value of element of
min_index. If value of element at index
jis less than value of element of
jbecomes the new
min_index = jif this is the case. Exit the inner loop.
- If value of new
min_indexis not equal to value of element at
ithen swap value of element at
iindex with value of element at
- Lastly, return the manipulated array.
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
- Check the input array length. If it is 0 or 1, return the array (already sorted!)
- If array length is greater than 1, then we want to define a mid-point, picked by choosing
array.length / 2and call a
floormethod so the number always rounds down.
- 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
midand ends at the last element. (Note: Ruby ranges
..are inclusive of the last element, whereas
...are exclusive of last element).
- Note that not only do I set
rightsubarrays equal to the lengths above, but they’re set to the
merge_sortversion of those subarrays. That means that
merge_sortwill be called upon these subarrays, which means picking a new midpoint, dividing the subarray into halves, and set
rightsubarrays that will call
- Lastly, I have a call to the
mergemethod to combine the left and right subarrays into one array.
Ruby Implementation — Merge
- Once the subarrays are broken down into the smallest pieces possible, now it’s time to sort and merge them together.
- If one of the two subarrays are empty, by default only information in the non-empty subarray is returned.
- 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
mergefunction call which takes
left[1..left.length],rightas the input parameters. It starts with the second element at index 1 since the first element has already been “sorted”.
- 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:
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.
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).
- First, our checks to see if
array.length <= 1.
- Pick a pivot at random. Ruby’s
delete_atmethod will delete the item at the specified index, which in this case would be a
randindex in the range of
array.length. We’re saving the value of that item to
- Create a new left and right subarray.
- Loop through every element in the array and compare it to the pivot. If the value is less than pivot, add element to the
leftsubarray. If value is greater than pivot, add element to the
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.
def heap_sort, we first build a max heap (lines 5–7).
- 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.
- At the end, we remake the array into its original size and revert the root back to index .
def heapifymethod will sift the elements until they’re in their rightful place.
parentindicates where to start sifting and
limittells how far down the heap to sift.
- 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
child could end up being out of bounds; in an array with 10 items, it’s possible to have
child = 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
array.length — 1 , adjust
downto(0), set swaps to be
a, a[n]= a[n],a, set loop to run while
n > 0, and pass
0 as the parent element in
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!