Insertion Sort Algorithm

Today I will talk about lesson 2 in Algorithms Unplugged which is insertion sort.

Insertion sort is an algorithm used to sort data in order. consider you have a bookcase with many books and you want to organize it to easily find a book when you need one so when you searching an unorganized bookcase it will depends on luck you may find it from the first try and you may check every book to find it if you are an unlucky person so sorting it will make you find it quickly and not it hadn’t to be your lucky day to find it😂.

There are many techniques you can follow to sort these books you can compare each two books and see if a book is less than another then it shall be before it and if it’s larger than then it shall remain after this book and keep doing so until you sort it not the most optimal one but it will sort the books at the end of the day. if you use such a technique you will have to exchange k(index of element) times the 2 books so in the worst case where you will have an array like this [4,3,2,1] sorting the last index will cause k exchanges (where k = 3).

Imagine you have an array of 1000 elements and the last element is the smallest one then you will have to do 999 exchanges between it and the other values of the array to make it sorted. So, in conclusion, this sort of algorithm is best when you have nearly sorted data.

calculating the time complexity for doing this algorithm in the worst case is nearly O(n²) but space complexity is constant O(1) the following equation calculates the time complexity needed by insertion sort :

Now we can start implementing insertion algorithm code we have two approaches The first is a less efficient technique:

The explanation of how this code works with example:

The second more efficient technique to implement is to consider the hand variable as your real hand that holds the book until you find the correct spot for the book and put it on the shelf so you will shift k+1 times one book and the number of exchanges you do will decrease here is the implementation of it:

The explanation of how it works:

And here it’s a summary of the second lesson in the Algorithms Unplugged book hope I have made it clear to anyone who has tackled problems with how the insertion sort algorithms work. The next lesson will be the fast sorting algorithms that are a more efficient way to sort your bookshelf so stay tuned😉.