Insertion Sort

Published about 8 years ago

Insertion sort! Insertion sort!?! Argh, I hear you saying, ‘why learn a sorting algorithm that has a one of the worst run times of the sort algorithms computer scientists are aware of.’ Well, to start, if you know that to be true, you likely don’t need a blog post to teach you about insertion sort. That being said, it’s true. Insertion sort is rarely, if ever the optimal sorting solution, so why learn it? Because it is a fundamental concept, or better yet a fundamental pattern that we as builders of software are likely to see often. The more familiar we are with this pattern on a fundamental level, the more likely we are to recognize it in the wild, and perhaps realize that there is a more optimal solution. I discussed the relevance of these fundamental Computer Science patterns in my previous article, Why CS for Web Devs?

Without further ado, let’s get into it. To think of insertion sort, the most common comparison is sorting a hand of cards. Most people do this intuitively, take one card at a time, working either left-to-right or right-to-left and place it in position among the cards already sorted.

The concept is fairly simple, so how do we convey it in code? One more illustration might help here. The animation below illustrates the algorithm very clearly.

Starting from the left, the first element can be considered sorted already, there is nothing to compare it to. Moving on to the second item we look behind it, to the left, we shift elements to the right until we find the place it fits, place it, then move on to the third element. Pretty straightforward. Now that we have a pretty good mental picture of how insertion sort works, let’s write some code.

The first step in designing this algorithm is fairly straightforward. We need to step through each element in the array. We do this with a simple for loop. See the code snippet below. Note that the for loop used is not very Ruby-esque, this was done on purpose, to highlight the fact that we aren’t iterating over the whole array. Instead, we assume that the first element is sorted, because we have no elements to compare it to. So we start with the second element of the array, i = 1. We set the current_element to the element at the current index, so we can overwrite it when we shift elements to the right and for inserting it back into the array when we find where it belongs. Finally we set the second pointer, j, to the element left of current_element, which has already been sorted.

def insertion_sort(array)
  # start with second element in array,
  # consider first element already sorted
  for i in 1...array.length
    current_element = array[i]
    j = i-1
  end
end

Now to compare the current_element to the previous, already sorted elements in the array. We have all the information we need thanks to the previous step, the current_element and the pointer, j, which we will decrement until one of two things occurs, we reach the front of the array and place the current_element there because it is smaller than all the other sorted elements, or we find an element that is smaller than the current_element and stop, because the current_element has found its place in line. All the while we are sliding each previous element at index j to the right to make a gap for our current_element with, array[j+1] = array[j]. See the gif above, for a reminder.

def insertion_sort(array)
  # start with second element in array,
  # consider first element already sorted
  for i in 1...array.length
    current_element = array[i]
    j = i-1

    # compare current_element to the elements to it's left
    # swap elements until current_element is in correct place
    while j >= 0 && array[j] > current_element
      array[j+1] = array[j]
      j = j-1
    end

    # we exited the while loop, indicating we found slot for
    # our current_element and place it accordingly
    array[j+1] = current_element
  end  
end

Hopefully, that cleared up the insertion sort for you if you had trouble understanding it before. In conclusion, I’d like to point out several details, gotchas, etc… with our algorithm. This algorithm mutates the array input, that is, it sorts the array in place. This is the most space efficient method. We could, however, create a new blank array to copy the elements into as we worked through the array given to us, this would allow us to leave the original array alone, but would take up double the space. This concept is what’s known as an algorithm’s space complexity.

Secondly, without diving too deep into the mathematics of runtime complexity, let’s see if we can at least glean an idea of what the worst case runtime might be based on some hints in the algorithm. Assuming that the size of the array is n elements. We know that at a minimum, we have to step through each element based on the for loop ( actually n-1 elements, but the 1 is negligible, especially as the size of the array gets to be huge ). Great, so we know that the algorithm’s big O is at least O(n). But wait, there is a while loop embedded inside that for loop, that complicates things. Envision an array that is sorted in reverse order. In that case we would have to iterate the for loop through every element in the array, and then iterate the while loop backwards through every element of the array. Whenever you have a for loop or a while loop, inside of another loop, you have basically multiplied your complexity by another factor of n ( there are exceptions to this rule, although, they are fairly uncommon ). So now we can say that the complexity of our algorithm is O(n * n) == O(n²). This is really a complex topic for another post, or series of posts.

Thanks for reading along, I’m eager to read your input. Perhaps you can write a non mutating version of this algorithm, implement the algorithm in another language, or even create an insertion sort for another data type such as a linked list. Until next time here are a few links that dive a little bit deeper into some of the concepts we discussed.

Insertion Sort

Big O Notation

Big-O Algorithm Complexity Cheat Sheet

In-Place Algorithm

Why CS for Web Devs?

Published about 8 years ago

If your a web developer you probably have pretty strong feelings about whether or not one needs a foundation in Computer Science, Data Structures, or Algorithms. A quick google search brings up countless results lamenting the current hiring process for web devs. Most arguing that web developers don’t need an understanding of data structures and algorithms, and never will. A significantly smaller number of articles exist extolling the benefits of a strong base in Computer Science for web developers.

I’m somewhere in the middle. There is no doubt that every web developer uses algorithms on a daily basis. If you have ever manipulated a string or an array in JavaScript, or any other language for that matter, you have used an algorithm, whether or not you knew how the algorithm actually accomplished its task. Ever written some code inside a for loop, yeah, you wrote an algorithm, even if it was as simple as logging the output of each value in the for loop. Do I, as a web developer need to know the inner workings of Ruby’s array sort algorithm to use it effectively? Of course not. Am I a better programmer in general when I understand how my tools work, and probably more importantly, why they don’t work in certain situations. I believe so.

As programmers, whether we are systems developers, full stack developers, mobile developers, embedded developers, or one of the countless other types of programmers, we deal with patterns.

The most fundamental patterns in Computer Science are the data structures and algorithms used to manipulate data at a low level. Whether it be stacks, queues, linked lists, or arrays, understanding these fundamental patterns allows us to identify similar patterns on a larger, or more abstract level. Clearly, at least a cursory understanding of the fundamentals of CS, can help us see patterns and solutions that we might otherwise not see.

As web development evolves, it tends toward more complexity, rather than less. Sure HTML and CSS are powerful tools that every front end web dev should master, in today’s landscape they simply aren’t enough. We need access to ever more powerful and complex tools to keep up with the ever changing landscape that is software development on the web. It’s difficult to be a good React, Angular, etc… developer without first understanding the basics of JavaScript. Similarly, it’s hard to really be a good JavaScript, Ruby, PHP, Python, etc… developer without understanding the fundamentals those languages are built on. These fundamentals, aka data structures and algorithms, get a bad rap. Many assume that since they are taught in university CS courses they are purely academic and difficult to learn. This is unfortunate. Although the concepts can be abstract, they don’t have to be difficult.

Maybe I’ve convinced you that having at least a basic understanding of the fundamentals of CS can help you be a better web developer, maybe you already knew, or maybe you are just eager to learn something new. Perhaps you’ve seen posts about CS concepts before written in a way that is too academic, or implemented in a language you don’t understand? If that’s the case stick with me, I aim to show you that these fundamental CS concepts can be learned in a way that gets away from the overly academic and more towards the fun stuff, that is, actually coding. Either way, join me in exploring a new topic in CS with each post. We will not only cover the basics but we will implement those basics. Get some hands on experience with these things to really understand them. Hope to see you next time.