Insertion Sort Algorithm in Data Structures

Insertion Sort is a simple technique to sort numbers in either ascending or descending order. It bears similarities to the sorting method used when playing cards during a game.

This sorting method is based on in-place comparisons. In this case, a consistently sorted sub-list is preserved. For instance, the lowest portion of an array is kept sorted. Once an element has been sorted, it must locate its proper place in the sub-list and be 'inserted' there. Thus, the term "Insertion Sort."

Unsorted items are transferred and added to the sorted sub-list (in the same array) when the array is successively searched. Because the average and worst-case complexity of this technique is O(n2), where n is the number of items, it is not appropriate for huge data sets.

In this article, we will have a broader look at the Insertion Sort Algorithm with examples. We will also discuss its advantages and characteristics.

Insertion Sort Algorithm

The Insertion Sort has a straightforward operating process. Students who may encounter questions based on the Insertion Sort will find this material to be highly informative and engaging. So, the subject must be discussed.

Sorting playing cards is comparable to how the Insertion Sort operates. In the card game, it is assumed that the first card has already been sorted. Next, we choose an unsorted card. The chosen unsorted card will be positioned on the right if it is larger than the first card; if not, it will be positioned on the left. Similarly, every unsorted card is removed and placed in its proper location.

The Insertion Sort uses a similar methodology. It works by iterating through the sorted array, starting with one element. Despite being easy to use, Insertion Sort is not suitable for large data sets because, in both the average and worst cases, the time complexity is O(n2), where n is the number of items. Compared to other sorting algorithms such as heap sort, fast sort, merge sort, the Insertion Sort is less efficient.

The Insertion Sort offers many benefits, including:

• Straightforward implementation
• Effective with small data sets
• Adaptive, meaning that it works well with data sets that have already undergone significant sorting.

Let's now examine the Insertion Sort Algorithm.

The Algorithm

The following is a list of the Insertion Sort Algorithm steps:

Step 1: Assume that the element has already been sorted if it is the first element. Go back to 1.

Step 2: Select the subsequent component and keep it apart in a key.

Step 3: At this point, compare each element in the sorted array with the key.

Step 4: Go to the next element if the element in the sorted array is smaller than the one you currently have. If not, move the array's larger elements to the right.

Step 5: Put the value in.

Step 6: Continue doing this until the array is sorted.

How does the Insertion Sort Algorithm Works?

Let's now examine how the Insertion Sort Algorithm operates.

Let's start with the example of an unsorted array.

Assume that the array's elements are:

First, an Insertion Sort comparison is made between the first two entries.

In this case, 31 is more than 12. Thus, both components are already arranged in ascending order. Therefore, 12 is currently kept in a sorted sub-array.

Proceed to the following two components and make a comparison.

In this case, 25 is less than 31. Therefore, 31 is in the wrong place. Now exchange 31 for 25. The Insertion Sort will help you check all of the elements in the sorted array, in addition to swapping.

There is currently only one element in the sorted array, which is 12. Therefore, 25 is more than 12. Therefore, even after swapping, the sorted array stays sorted.

There are now two elements—12 and 25—in the sorted array. Proceed to the following elements, which are 8 and 31.

8 and 31 are not sorted. Change them.

Now, elements 25 and 8 are unsorted after switching.

Therefore, switch them.

Elements 8 and 12 are currently unsorted.

Thus, switch them as well.

There are now three elements in the sorted array: 8, 12, and 25. Proceed to items 31 and 32.

They have already been sorted. The sorted array now consists of 8, 12, 25, and 31.

Proceed to the following items, 32 and 17.

32 is larger than 17. Change them, then.

By swapping, 31 and 17 become unsorted. Thus, switch them as well.

After exchanging, 25 and 17 are no longer sorted. Therefore, go ahead and switch again.

The array has now been thoroughly sorted.

The Complexity of Insertion Sort

Let's now examine the time complexity of the Insertion Sort in the best, average, and worst cases. We will also examine the space complexity of the Insertion Sort.

1. Space Complexity

O(1) is the space complexity of the Insertion Sort. This is because swapping in the Insertion Sort requires the usage of an additional variable.

2. Time Complexity

As we have indicated, Insertion Sort is an efficient sorting algorithm because it only utilizes one while loop—rather than several while loops—to prevent additional steps after the array has been sorted. This allows the algorithm to operate on predetermined conditions.

The Insertion Sort Algorithm is efficient. But, if we give it an array that has already been sorted, it will still execute the outer for loop. This means that it will take n steps to sort an array of n elements that have already been sorted, meaning that in the best-case scenario, its time complexity is a linear function of n.

This is usually in three cases:

• Best Case Complexity: This happens when the array is already sorted and no sorting is necessary. Insertion Sort's best-case temporal complexity is O(n).

• Average Case Complexity: This is the result of an array's components being arranged in an inconsistent manner, which are neither correctly ascending nor properly descending. Insertion Sort's average case time complexity is O(n2).

• Worst Case Complexity: The worst case complexity is when sorting the array elements backward is necessary. In other words, let's say that the array's descendingly arranged components need to be sorted in an ascending order. Insertion Sort's worst-case temporal complexity is O(n2).
  

How to Implement the Insertion Sort Algorithm in Data Structure

Let's now examine the various types of algorithm for Insertion Sort in data structure and their application in several programming languages:

1. Insertion Sort Algorithm in C

The following is an example of C program, which demonstrates the implementation of Insertion Sort Algorithm:

#include <stdio.h>

void insert(int a[], int n) /* function to sort an aay with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;

while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);

return 0;
}

Output:

Before sorting array elements are -
12 31 25 8 32 17
After sorting array elements are -
8 12 17 25 31 32

2. The Insertion Sort Algorithm in Python

The following is a program that shows the implementation of Insertion Sort in python:

def insertionSort(a): # Function to implement insertion sort
for i in range(1, len(a)):
temp = a[i]

# Move the elements greater than temp to one position
#ahead from their current position
j = i-1
while j >= 0 and temp < a[j] :
a[j + 1] = a[j]
j = j-1
a[j + 1] = temp

def printArr(a): # function to print the array

for i in range(len(a)):
print (a[i], end = " ")

a = [70, 15, 2, 51, 60]
print("Before sorting array elements are - ")
printArr(a)
insertionSort(a)
print("\nAfter sorting array elements are - ")
printArr(a)

Output:

Before sorting array elements are -
70 15 2 51 60
After sorting array elements are -
2 15 51 60 70

3. An Insertion Sort Algorithm Pseudocode in C++

#include <iostream>
using namespace std;

void insert(int a[], int n) /* function to sort an aay with insertion sort */
{

int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;

while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
cout << a[i] <<" ";
}

int main()
{
int a[] = { 89, 45, 35, 8, 12, 2 };
int n = sizeof(a) / sizeof(a[0]);
cout<<"Before sorting array elements are - "<<endl;
printArr(a, n);
insert(a, n);
cout<<"\nAfter sorting array elements are - "<<endl;
printArr(a, n);

return 0;
}

Output:

Before sorting array elements are -
89 45 35 8 12 2
After sorting array elements are -
2 8 12 35 45 89

Crucial Characteristics of Insertion Sort

The key features of Insertion Sort are:

1. It is efficient for smaller data sets and ineffective for the larger ones.
2. The adaptability of the Insertion Sort adds to its efficiency, which implies that if an array that has been partially sorted is supplied as input, it will take less steps overall.
3. Compared to Bubble Sort and Selection Sort algorithms, it performs better.
4. It has reduced spatial complexity. Insertion Sort needs one extra memory space, much like bubble sort.
5. Because it maintains the relative order of equal elements, it is a stable sorting technique.
   

What Advantages Does the Insertion Sort Offer?

Let us now examine the key advantages of employing the Insertion Sort and situations where it proves to be the best:

• Similar to other quadratic sorting algorithms, it is effective with tiny amounts of data.
• All it needs is a fixed quantity of O(1) more memory.
• It functions best with data sets that have undergone extensive sorting.
• The relative order of elements that share the same key is unaffected.
  

What Disadvantages Does the Insertion Sort Have?

Although Insertion Sort is easy to use and works well for smaller data sets, it has certain drawbacks. We'll now discuss a few significant disadvantages that you should be aware of before implementing insertion Sort in real-time.

• Insertion Sort is ineffective when applied to larger data sets.
• The worst-case O(n2) temporal complexity is demonstrated by the Insertion Sort.
• Compared to other, more sophisticated sorting algorithms, it performs worse.
  

Conclusion

The Insertion Sort Algorithm offers a straightforward and efficient method for sorting elements, resembling the process of arranging playing cards.

Its in-place comparison approach preserves a sorted sub-list within the array, making it suitable for small datasets and partially sorted collections. However, its time complexity of O(n^2) in average and worst cases limits its efficiency for large datasets compared to other sorting algorithms like merge sort or quick sort.

Despite its limitations, understanding and implementing insertion sort is valuable for grasping fundamental sorting concepts and can be advantageous in certain scenarios.

Frequently Asked Questions

1. Explain the Insertion Sort with an example.

Insertion Sort iterates through an array, moving each element into its proper position within a sorted subarray. For instance, in [5, 2, 4, 6, 1, 3]:

• Start with the second element (2).
• Compare it with the elements before it.
• If smaller, shift larger elements right.
• Repeat until they are in the correct position.
• Result: [1, 2, 3, 4, 5, 6].
  

2. What are the sorting algorithms in data structure?

Sorting algorithms in data structure include various methods such as bubble sort, selection sort, merge sort, quick sort, and Insertion Sort.

3. What is the Insertion Sort sometimes called?

Insertion Sort is sometimes referred to as the ‘Straight Insertion Sort.’

4. How many parts does an Insertion Sort Algorithm consist of?

The Insertion Sort algorithm consists of two main parts: the sorted subarray and the unsorted subarray.

5. What is the Insertion Sort Algorithm in simple explanation?

The Insertion Sort algorithm works by iteratively inserting each element into its proper position within a sorted subarray, resulting in a fully sorted array.

6. What are the three steps of the Insertion Sort Algorithm?

The Insertion Sort Algorithm consists of three main steps:

• Initialization: Start with the second element of the array.
• Comparison and Shifting: Compare the current element with the elements before it, shifting larger elements to the right until finding the correct position for insertion.
• Insertion: Insert the current element into its proper sorted position within the array.