In computer science, few tools are used quite as often as sorting algorithms. We rely on them every day as programmers and engineers to sift through data, and they're built into nearly every modern programming language in one way or another.
While using a language's built-in sorting functions may get the job done for most day-to-day work, it's important to understand what's going on under the hood, and what different sorting algorithms are actually doing and why they work the way they do. While it may not come up often, there's always the chance you may be asked to implement or explain a sorting algorithm in a technical interview setting, which is exactly what this post is here to prepare you for!
Today, we'll be looking at Insertion Sort, one of the fundamental sorting algorithms in Computer Science.
What is Insertion Sort?
As the Wikipedia page of the algorithm describes:
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. ... Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.
This might sound a bit confusing, but here's a helpful visualization of what the algorithm will be doing with data:
As we move through an array of integers, each value will be compared one at a time to the previous integers that come before it, swapping places with each one until it has eventually been inserted into its proper place.
We wind up with two sub arrays as we work through the data, with the left side being sorted and the right side remaining unsorted.
How efficient is it?
Unfortunately Insertion Sort is less efficient in large data sets than more advanced algorithms like Quick Sort, Heap Sort, or Merge Sort, although it does have certain advantages.
- Simple to implement, programmatically.
- Efficient for small data sets.
- Adaptively efficient for data sets that are already mostly sorted.
- Functions in-place, taking only constant O(1) space.
The worst case and average case time complexity of Insertion Sort are both O(n2) (quadratic.)
How do we implement it?
Now we're getting to the good part!
Since we're implementing Insertion Sort in JavaScript, we'll be making use of modern ES6+ syntax to handle swapping elements in the array, which will help keep the number of lines of code that we need to write down.
Here's what the final algorithm will look like:
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let j = i;
while (j > 0 && array[j] < array[j - 1]) {
[array[j - 1], array[j]] = [array[j], array[j - 1]];
j--;
}
}
return array;
}
Now, let's break it down step by step.
First off, let's declare our function, its return value (the modified array), and the main for loop in which we'll be doing all of our logic:
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
}
return array;
}
We're writing this as a pretty predictable for loop that simply iterates through our entire array. The difference here is that we'll be starting at index 1 instead of the usual 0. This is because we're always going to compare each element to at least the one that comes before it to see if a swap is necessary. Since the 0th element doesn't have a previous one to compare to, we skip it and start at 1.
Next, we establish a second pointer for our traversal through the array, j:
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let j = i;
}
return array;
}
Pointer j is set to the value of i, because as we traverse forward through the array in our for loop, we'll also implement a second while loop in a moment that traverses backward to compare it to each value in the already sorted sub array.
That while loop, and the final step of our algorithm, looks like this:
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let j = i;
while (j > 0 && array[j] < array[j - 1]) {
[array[j - 1], array[j]] = [array[j], array[j - 1]];
j--;
}
}
return array;
}
This is a lot of new code, so let's work through what all 3 lines of it do.
- We implement a while loop that will fire off while j is greater than 0 (meaning it hasn't reached the beginning of the array) AND while the value of array[j] is less than array[j - 1]. These two conditions will allow the loop to traverse all the way down the array, swapping values until the starting element has been inserted into its proper place (the element before it being of lesser value.)
- We use JavaScript ES6 syntax to swap each element with the element that comes before it, moving the starting element down the array one step at a time.
- We decrement the value of j, so that on our next loop we're still swapping the same element that we started with further down.
And that's it! We've now successfuly implemented an Insertion Sort algorithm in JavaScript. Hooray!
This is all a lot to visualize and wrap your head around, so I encourage you to think about the loops and pointers to get a real sense of what's happening-- once it clicks you'll have it locked in for good. I'll re-paste this helpful animation here as well, since I think it helps a lot to visualize what's being done:
If you've come this far, thanks so much for reading! I hope this was a helpful tutorial to anyone learning about sorting algorithms, JavaScript, or programming fundamentals in general.
I'll continue working through more sorting algorithms in future posts, so stay tuned!
Top comments (2)
I know this is like more than two years later. But please let me know if you got the tutorials on a Github repo. This is perhaps the best explanation I've read in a long time and I'll definitely use the Github repo and share it.
Thank you so much! I appreciate the comment. I hadn't actually considered making these tutorials into GitHub repos before, but I'm definitely going to look into that now. 😄