Data Structure: Insertion Sort

What is Insertion Sort?

In this particular blog, we’ll be talking about the Insertion Sort technique. This method takes elements in random order and sorts them based on the comparison. One way to think about this algorithm from a different perspective is to imagine if you were given a handful of cards, your immediate instinct is to sort them from ascending order. It’s highly intuitive and a comparison-type algorithm. However, the downside would be the time complexity which is O(n²). This method is deemed to be the worst-case scenario.

How Does it Work?

Start with creating an accessible variable called temp.

Iterate through the array starting at the index of 1. Within that first iteration well set temp to the current index of the array.

This next step requires iteration, however, there is a particular trick to this because we will be setting a condition within the loop.

We will start with a second iteration, which consists of starting at the index before our first index of the first iteration. Furthermore, we will add a condition of if the index before the current array is greater than the actual current array. It will look more like this.

There is an important trick in this particular loop that is overlooked. The index of j has to be greater than -1. This is implemented because if the loop is continuously comparing and sorting the order of the elements it will eventually go beyond the index of 0 to -1. Therefore we added a condition of the index of j must be greater than -1.

Once the second iteration is established and conditions are met, we will move the index of j over 1 in place of temp.

We will then break out of the for loop and put temp in the open spot. Once everything checks out we will return the array.

Here is a full look at the solution below. Hoped you guys enjoyed it till next time.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store