Insertion Sort in Ruby

I was looking back through my sorting series in Ruby, and I can't believe I haven't gone over insertion sort yet! I feel that this is a pretty common sorting algorithm and definitely a good one to add to the series.

Without further ado, here is insertion sort!

Overview

First, a little overview about the insertion sort algorithm:

• Insertion sort is an in-place sorting algorithm
  • A new array will not be created in order to hold the new sorted values
• Insertion sort is also a stable sorting algorithm
  • This essentially means that duplicate values in the array will appear in the same order that they did originally

Time Complexity

Like every good algorithm that would ever be needed in any good coding interview, we have to discuss the time complexity.

Time	Case
O(n2)	average case run time
O(n2)	worst case run time
O(n)	best case run time

Insertion sort, similar to the other sorting methods we've gone over, isn't really optimizing for time complexity. The best case for insertion sort is O(n), and that is if most if not all the elements are already sorted. The worst case is if the elements are in reverse sorted order.

Each value needs to be iterated over at least once, and if we have n values in the array, that easily becomes O(n²). Insertion sort would be very fairly ineffective on large arrays.

In comparison, insertion sort's space complexity isn't awful in terms of auxiliary space. The overall space complexity is still O(n), but it's auxiliary space is O(1), meaning that it does not use up much temporary space to sort the elements.

Theory/Break Down

Now for the theory of the insertion sort algorithm. When I say theory I find it the most helpful to visualize what the actual process is and then we can code it up.

I think that GeeksforGeeks gave an awesome example of an easy way to visualize insertion sort. They described it as the same way you would sort cards in your hand. I absolutely loved that and it makes it very clear how insertion sort works.

Basically we walk through the array looking for a number that is smaller than the number we're currently iterating over. When we find that number we determine where it should be placed by comparing it to all of the numbers that have been already sorted and are to the left of the number we are iterating over.

All of the numbers that are greater than the element we are iterating over will be shifted to the right to make space for the sorted element.

Essentially the array is broken in half, one side is sorted and the other isn't. We continue moving across the unsorted portion, inserting the elements where they belong, until the entire array is sorted.

Actual Code

Alright, on to the part you've been probably waiting for, the code! I have two implementations of insertion sort in Ruby and you can feel free to play with them both and see which makes more sense to you. Both are very similar, using two loops, but differ slightly in syntax, so please change it around to whatever works best for you.

Implementation 1: from rubyalgo

def insertion_sort(array)
    for i in 1...(array.length)
        j = i
        while j > 0
            if array[j-1] > array[j]
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            else
                break
            end
            j = j - 1
        end
    end
    return array
end

In this implementation, we will first iterate through the array using our interval variable i. Next we will create our interval variable j, which will start the same as i, but decrease as we iterate over the sorted side of our array.

We check if the value to the left of our current interval j is greater than the actual value of j, and if so we will move it to the right as many times as necessary to correctly place our current interval. This is why we need j to iterate over the sorted portion of the array until we can find where the current interval j's correct position is.

Implementation 2: adapted from mycodeschool on Youtube (link is below)

def insertion_sort(array)
    for i in 1...(array.length)
        value = array[i]
        temp = i
        while temp > 0 && array[temp - 1] > value
            array[temp] = array[temp - 1]
            temp = temp - 1
        end
        array[temp] = value
    end
    return array
end

For the second implementation we will again first iterate through the array. But this time we will create two new variables, value to hold the value that we are looking to insert correctly, and temp, the space that will determine where the held value will eventually end up.

We check that there is indeed a sorted half already by ensuring i or temp is greater than 0. Then we also check that the value of the index to the left the interval we are on is greater than the value we are holding. That way we know that we will need to move the current interval to the left and that the larger value will need to move to the right. This continues until the array is sorted.

Resources

• Geeks for Geeks explanation
• mycodeschool on Youtube's video walkthrough

I hope that this could be helpful for you and I'll catch you for the next installment of my sorting algorithm series! Happy coding 😊