Algorithms — Insertion Sort

Today we will be discussing the sorting algorithm known as the Insertion Sort. When I first began my coding journey I thought I would be able to get by without diving deep into topics like design patterns and algorithms. I soon realized that not only are these topics essential, they are also very beneficial when it comes to developing a deeper understanding of writing code. So why learn algorithms? In programming, algorithms mimic real life problems and provide real life solutions to those problems. Not only do algorithms help deepen your understanding of writing code, they also help you solve common problems you will encounter while creating applications. They are great mental exercises and they force you to plan ahead before diving straight into your code. Let’s take a look at a common sorting algorithm, the Insertion Sort algorithm.

What is the Insertion Sort Algorithm?

The Insertion Sort algorithm is an algorithm used to sort a list of items into ascending or descending order. The way the algorithm works is similar to the way someone playing cards would sort their hand of cards. It works by comparing the current element with the elements to its left. If the current element is determined to be larger than the element to its left, it will insert the current element in front of the smaller element.

Step-By-Step

1. Assume the first element is already in place
2. Pick the next element in the list
3. Compare with all the elements in the sorted sub-list (all the elements to its left)
4. Shift all the elements in the sorted sub-list that are greater than the current element
5. Insert the value into the list where the element to its left is smaller, and the element to its right is larger
6. Repeat until the list is sorted

When should the Insertion Sort Algorithm be used?

To determine when this algorithm should be used, we should take a look at its time complexity. In the best-case scenario, this algorithms time complexity will be O(n), Linear time complexity. This only occurs if the list going through the algorithm is already in the correct order. In the worst case scenario, the time complexity for this algorithm is O(n²), quadratic time complexity. This will occur if the elements are jumbled, or if it is completely in the reverse order that we want it to be.

This means that this algorithm should only be used with smaller data sets because an algorithm with quadratic time complexity can take a very long time when working with large data sets. With smaller data sets however, this algorithm is quick, efficient, and very easy to implement.

How to use the Insertion Sort Algorithm?

I’d like to demonstrate this algorithm using Javascript. Take a look at the code below to see my example.

const insertionSort = (arr) => {

    // determine the length of the input
    let len = arr.length;

    // iterate through the array
    for (var i = 1; i < len; i++) {
        
        // save the current element we are evaluating
        let current = arr[i];

        // determine the index of the previous element
        let j = i - 1;

        // while the index of the previous element is greater than -1 (beginning of the list)
        // and the current element is less than the previous element
        // swap the elements and decrease j by 1
        while ((j > -1) && (current < arr[j])) {
            // swap
            arr[j + 1] = arr[j];
            j--;
        };

        // swap
        arr[j+1] = current;
        
    };
    return arr;
};

Great! We’ve got out algorithm, let’s make sure it works.

let nums = [5,23,54,7,87,2,4,32,8,56,98,43,45,12,21,69,36,25];

console.log(insertionSort(nums));
// [2, 4, 5, 7, 8, 12, 21, 23, 25, 32, 36, 43, 45, 54, 56, 69, 87, 98]

After running our array of nums through our insertionSort algorithm, we get a sorted array returned to us.

Conclusion

In this article, we discussed the Insertion Sort Algorithm. We discussed what the algorithm is, how it works, and determined when we should and shouldn’t use it. I hope you enjoyed this article, and even learned something new! Keep learning, and happy coding!