Insertion Sort in Data Structures

Amit Kumar Ghosh 17 min read

14 Jun 2023

Intermediate

341 Views

Insertion Sort

Introduction

Regarding data structures and efficient sorting, Insertion Sort is a vital algorithm that you need to be familiar with. It's an incredibly powerful concept in computer science. It allows us to sort any group of elements in ascending or descending order in linear time. Insertion sort is relied upon for its simplicity and versatility from small lists and simple tasks to full-scale sorting operations, insertion sort can reliably do the job! Despite some potential downsides, when used correctly it is one of the most advantageous algorithms for sorting data structures. In this article, we'll explore exactly how Insertion Sort works.

What is insertion sort in Data Structure

Sorting is a crucial task in computer science, and insertion sort is an important algorithm for it. In simple terms, insertion sort in data structure runs through a list of numbers and sorts them one by one. It works by comparing each item in the list and inserting it in its correct position until it has iterated through the entire list. While it may not be the most efficient sorting algorithm out there, it can still be useful for smaller datasets or as a building block for more complex algorithms. By understanding how insertion sort works, we can gain a better understanding of how sorting algorithms function and how to optimize them for different scenarios.

How does insertion sort work?

Insertion Sort is a simple sorting algorithm that works by building the final sorted array one item at a time. It iterates through an array of elements, comparing each item with the previous ones, and placing it in the correct position.

Here are the steps involved in how Insertion Sort works:

Initial Array: [8,12,20,18,32]

Start with the second element of the array, assuming the first element is already sorted.

Compare the second element with the first element. If the second element is smaller than the first, swap them. Otherwise, leave them as they are.

Move to the third element of the array, and compare it with the second element. If the third element is smaller than the second, swap them. If not, compare it with the first element and swap it if necessary.

Continue this process for all elements of the array, moving from left to right. At each step, compare the current element with the previous ones and place it in the correct position.

After all the elements have been sorted, the array will be in ascending order.

Insertion sort complexity

There are two types of Insertion sort complexity, are:

The time complexity of the Insertion Sort algorithm: The time complexity of the Insertion Sort algorithm is O(n^2) in the worst case, where n is the number of elements in the input array. The reason for this is that for each element in the array, the algorithm iterates over all the previous elements in the array until it finds the correct position to insert the current element. This results in an inner loop with a maximum of n-1 iterations for each outer loop iteration. Therefore, the total number of comparisons performed by the algorithm is roughly proportional to n^2. However, in the best case, when the input array is already sorted, the time complexity of Insertion Sort is O(n), since the inner loop will not execute at all.
The space complexity of the Insertion Sort algorithm: The space complexity of the Insertion Sort algorithm is O(1) or constant space complexity, which means that the amount of additional space required by the algorithm is the same regardless of the size of the input data. Insertion Sort algorithm sorts the elements in place, that is, it rearranges the elements within the given array, without using any additional memory other than a few constant variables. The algorithm scans through the array one element at a time, and swaps elements as necessary to sort the array. Therefore, the space complexity of Insertion Sort is constant, and it does not depend on the size of the input array. The amount of space required by the algorithm remains the same, regardless of the size of the input data.

Application of Insertion Sort

The Applications of Insertion Sort are:

Small Datasets: Insertion Sort is efficient for sorting small datasets or lists with a small number of elements. It is faster than other sorting algorithms such as Merge Sort or Quick Sort when the input size is small.
Partially Sorted Arrays: If the input array is already partially sorted, then insertion sort working can be used to sort the remaining unsorted elements efficiently. This is because Insertion Sort has a linear time complexity when the input array is already sorted or almost sorted.
Online Algorithms: Insertion Sort is an online algorithm, which means it can sort a list as it receives it. This is useful in applications where the input data is continuously arriving, and sorting needs to be performed on the fly.
Adaptive Sorting: Insertion Sort is an adaptive sorting algorithm, which means it can quickly adapt to changes in the input data. For example, if the input data is almost sorted, then Insertion Sort can quickly identify this and sort the remaining unsorted elements efficiently.
In-Place Sorting: Insertion Sort is an in-place sorting algorithm, which means it sorts the input list without using any additional memory. This makes it ideal for sorting large datasets that cannot fit into memory.

Insertion sort algorithm

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort


 # Insertion sort in Python
 def insertionSort(array):
 
     for step in range(1, len(array)):
         key = array[step]
         j = step - 1
 
         # Compare key with each element on the left of it until an element smaller than it is found
         # For descending order, change key<array[j] to key>array[j]. 
         while j >= 0 and key < array[j]:
             array[j + 1] = array[j]
             j = j - 1
 
         # Place key at after the element just smaller than it.
         array[j + 1] = key
 
 
 data = [7, 5, 1, 6, 10]
 insertionSort(data)
 print('Sorted Array in Ascending Order:')
 print(data)


 // Selection sort in Java

 import java.util.Arrays;
 
 class SelectionSort {
   void selectionSort(int array[]) {
     int size = array.length;
 
     for (int step = 0; step < size - 1; step++) {
       int min_idx = step;
 
       for (int i = step + 1; i < size; i++) {
 
         // To sort in descending order, change > to < in this line.
         // Select the minimum element in each loop.
         if (array[i] < array[min_idx]) {
           min_idx = i;
         }
       }
 
       // put min at the correct position
       int temp = array[step];
       array[step] = array[min_idx];
       array[min_idx] = temp;
     }
   }
 
   // driver code
   public static void main(String args[]) {
     int[] data = { 280, 117, 9, 12, 4 };
     SelectionSort ss = new SelectionSort();
     ss.selectionSort(data);
     System.out.println("Sorted Array in Ascending Order: ");
     System.out.println(Arrays.toString(data));
   }
 }


 /p>// Selection sort in C++

 #include <iostream>
 using namespace std;
 
 // function to swap the the position of two elements
 void swap(int *a, int *b) {
   int temp = *a;
   *a = *b;
   *b = temp;
 }
 
 // function to print an array
 void printArray(int array[], int size) {
   for (int i = 0; i < size; i++) {
     cout << array[i] << " ";
   }
   cout << endl;
 }
 
 void selectionSort(int array[], int size) {
   for (int step = 0; step < size - 1; step++) {
     int min_idx = step;
     for (int i = step + 1; i < size; i++) {
 
       // To sort in descending order, change > to < in this line.
       // Select the minimum element in each loop.
       if (array[i] < array[min_idx])
         min_idx = i;
     }
 
     // put min at the correct position
     swap(&array[min_idx], &array[step]);
   }
 }
 
 // driver code
 int main() {
   int data[] = {280, 117, 9, 12, 4};
   int size = sizeof(data) / sizeof(data[0]);
   selectionSort(data, size);
   cout << "Sorted array in Acsending Order:\n";
   printArray(data, size);
 }

Output

Sorted array in ascending order:
1, 5, 6, 7, 10

Advantages of insertion sort

There are some advantages of insertion sort, those are

Easy to implement: Insertion sort is easy to understand and implement compared to other complex sorting algorithms like quicksort or mergesort.
Space efficiency: Insertion sort has a space complexity of O(1) since it sorts the input array in place, meaning that it does not require any additional memory to sort the elements.
Adaptive: Insertion sort is adaptive, meaning that it performs better on partially sorted arrays. This is because it can quickly detect when an element is in its correct position and move on to the next one, leading to faster sorting times.
Online sorting: Insertion sort is an online sorting algorithm, which means that it can sort data as it is received, without having to wait for all the data to be collected. This makes it useful in situations where data is continuously being generated, such as in live data streams or real-time data processing.
Best for small arrays: Insertion sort works well for small arrays with a few elements, where its simplicity and speed make it an optimal choice.
Stable: Insertion sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output as they were in the input.

Disadvantages of insertion sort

There are some disadvantages of insertion sort, those are

Performance on large lists: Insertion sort has a time complexity of O(n^2) in the worst-case scenario, which makes it inefficient for large lists. As the size of the input increases, the time taken to sort the list also increases significantly. This makes insertion sort less suitable for large-scale applications.
Not suitable for parallel processing: Insertion sort is an inherently sequential algorithm, which means it cannot take advantage of parallel processing. This makes it less suitable for high-performance computing applications where parallelism is important.
Less efficient than other sorting algorithms: There are many other sorting algorithms that are more efficient than insertion sort for large lists. For example, merge sort and quicksort have a time complexity of O(n log n), which makes them much faster than insertion sort for large lists.
Sensitivity to initial ordering: Insertion sort performs poorly when the input list is already partially sorted or nearly sorted. In such cases, the algorithm still performs O(n^2) operations, which makes it less efficient than other algorithms that are not sensitive to initial ordering.
In-place sorting: Insertion sort requires that the input list be sorted in place, which means that it cannot use extra memory to store intermediate results. This makes it less suitable for applications where memory usage is a concern.

Summary

Insertion sort is a powerful data structure that can help you better organize and store complex information. It offers versatility in terms of sorting, as it’s capable of sorting various types of data. The algorithm also performs quickly compared to other sorting algorithms, which makes it a great choice for efficiently organizing large sets of data. The main downside to insertion sort is that it may not be the most memory-efficient method. With careful consideration and savvy implementation, however, insertion sort can still do wonders for compacting large datasets while delivering optimal performance. Now that you’ve learned the basics of insertion sort in data structures, why don’t you try this powerful tool in your next project? With a little practice, you could find yourself more organized and efficient than ever before!