Insertion Sort Algorithm Analysis

For Complete YouTube Video: Click Here

In this class, we will try to understand Insertion Sort Algorithm Analysis.

We have discussed the analysis of the selection and bubble sort.

The prerequisite for this course is a data structures course.

The image below is the algorithm for insertion sort.

The above image’s first line of code is a “for” loop.

The for loop will iterate n times.

Every time we enter the loop key = A[j] and i = j – 1 will be executed.

The step count for the above two lines of code is n – 1 each.

The step count for the while loop is very crucial to understand.

The comparision in the conditional part of the while loop is i < -1 and A[i] > key.

The while loop will iterate based on the value of j.

i < -1 condition states that no other elements can be compared.

A[i] > key is valid, meaning the array’s element is larger than the key element.

In such a case, the array’s element must be moved ahead.

Now, we will consider the number of iterations done by the while loop.

If the value of j = 1 means, the while loop will iterate for one time.

If the value of j = 2 means, the while loop will iterate two times.

Similarly, If the value of j = n means, the while loop will iterate for n -1 times.

If we summarize all the iterations, it will be 1 + 2 + 3 + …. + n -1.

The above series looks like the sum of the first “n – 1” natural numbers.

The formula for the sum of first “n – 1” natural numbers is n(n – 1) / 2.

If we expand the above equation, the higher order term is n².

If we summarize the step count of all the lines in the algorithm, the higher order term is n².

The efficiency of the insertion sort algorithm is n².

Now, we will consider the best and worst-case scenarios, as shown below.

In the best-case scenario, the A[i] > key will fail in every case.

So, the step count for the while loop is n.

In the worst case, all the iterations are done as discussed above.

The efficiency of the insertion sort algorithm is n².