Insertion Sort in Data Structure

The name “Insertion Sort” comes from the notion of inserting an element at a certain location. Insertion sort is based on the assumption that in each iteration, one element from the input elements is consumed in order to determine its correct location in a sorted array. It iterates through the input elements, expanding the sorted array each time. It compares the current element to the sorted array’s greatest value. If the current element is greater, it remains in place and continues on to the next element; otherwise, it locates the element’s correct location in the sorted array and transfers it there. This is accomplished by moving any elements in the sorted array that are greater than the current element one place forward.

Working of Insertion Sort

Insertion Sort involves the following process:

1. The first step is to compare the element in question to its neighboring element.

2. If each comparison finds that the element in question can be inserted in a specific location, space is created for it by relocating the other items one position to the right and inserting the element in the appropriate location.

3. The operation is continued until all of the array’s elements are in their proper positions.

Let’s look at an example to understand how to work, where an unsorted array is as shown below.

The first two elements are compared in insertion sort.

It discovers that 15 and 34 are already arranged in ascending order. For the time being, 15 is in the sorted sub-list.

Insertion sort advances to the next step, comparing 34 to 28. And it turns out that 34 isn’t at the right spot. It replaces the number 34 with the number 28. It also double-checks all of the elements in the sorted sub-list. We can see that there is only one element 15 in the sorted sub-list, and 28 is greater than 15. As a result, even after swapping, the sorted sub-list remains sorted.

In the sorted sub-list, we now have 15 and 28.

It then compares 34 to 11. These numbers aren’t arranged in any specified sequence. So we swap them around.

Swapping, on the other hand, leaves 11 and 28 unsorted.

As a result, we swap them as well and we observe 15 and 11 in an unsorted arrangement once more.

We swap them around once again. We have a sorted sub-list of four items at the end of the third iteration.

This process continues until a sorted sub-list contains all of the unsorted data.

Insertion Sort Algorithm

Let ARRAY is an array with N elements

1. Read ARRAY
2. Repeat step 3 to 8 for I=1 to N-1
3. Set Temp=ARRAY[I]
4. Set J=I-1
5. Repeat step 6 and 7 while Temp<ARRAY[J] AND J>=0
6. Set ARRAY[J+1]=ARRAY[J] [Moves element forward]
7. Set J=J-1 [End of step 5 loop]
8. Set ARRAY[J+1]=Temp [Insert element in proper place] [End of step 2 loop]
9. Exit

Complexity of Insertion Sort

Insertion sort is a fast sorting algorithm since it doesn’t utilize for loops to execute on preset conditions; instead, it employs a single while loop to prevent additional steps once the array is sorted. Despite the fact that insertion sort is efficient, if we give it an already sorted array, it will still execute the outer for loop, requiring n steps to sort an already sorted array of n elements, making its best case time complexity a linear function of n.

• Time Complexity in the Worst Case (Big-O): O(n²)

• Time Complexity in the Best Case (Big-omega): O(n)

• Average Case Time Complexity (Big-theta): O (n²)

• Space Complexity: O(1)

Characteristics of Insertion Sort

•  It works well for smaller data sets but not so well for longer lists.

• Insertion Sort is adjustable, which means that if a partially sorted array is provided as input, it reduces the overall number of steps, making it more efficient.

• It outperforms the Bubble Sort and Selection Sort algorithms.

• It is a stable sorting strategy since it does not alter the relative order of equal elements.

• Insertion sort, like bubble Sort, requires a single additional memory space. It has lower space complexity.