Insertion Sort Analysis

7 February 26, 2023

Hi everyone, inside this article we will see the concept about Insertion Sort Analysis.

Insertion sort is a simple sorting algorithm that works by building a sorted array one element at a time. It is a comparison-based algorithm that compares each element with the elements in the sorted subarray to find its correct position.

The algorithm maintains a sorted subarray in the lower part of the array and inserts the remaining elements one by one into their correct positions in the subarray.

Algorithm of Insertion Sort

The algorithm for Insertion Sort is as follows:

Start with the second element of the array and consider it as the first element of a sorted subarray.
Compare the current element with the elements of the sorted subarray, starting from the end and moving towards the beginning.
If the current element is smaller than an element of the sorted subarray, shift that element to the right and continue the comparison with the next element of the sorted subarray.
If the current element is greater than or equal to an element of the sorted subarray, insert the current element at the position immediately after that element and terminate the loop.
Repeat steps 2-4 for the remaining unsorted elements of the array.
The array is now sorted.

The pseudo-code for the insertion sort algorithm is as follows:

for i from 1 to n-1 do
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key do
        A[j+1] = A[j]
        j = j - 1
    end while
    A[j+1] = key
end for

In this pseudo-code, A is the array to be sorted, n is the length of the array, and key is the current element being inserted into the sorted subarray. The loop variable i iterates over the unsorted elements of the array, while the loop variable j iterates over the sorted subarray, comparing the current element with each element of the sorted subarray until the correct position is found for insertion. Once the correct position is found, the current element is inserted at that position.

How does Insertion Sort Work?

Here is an example of how insertion sort works on an array of integers:

Input array: [5, 2, 4, 6, 1, 3]

Start with the first element (5), which is already sorted.
Compare the second element (2) with the first element (5) and swap them: [2, 5, 4, 6, 1, 3]
Consider the first two elements as the sorted subarray (2, 5) and compare the third element (4) with them.
4 is greater than 2 but less than 5, so it should be inserted between them. Shift 5 to the right and insert 4: [2, 4, 5, 6, 1, 3]
Consider the first three elements as the sorted subarray (2, 4, 5) and compare the fourth element (6) with them.
6 is greater than 5, so it is already in the correct position. The sorted subarray is still (2, 4, 5).
Consider the first four elements as the sorted subarray (2, 4, 5, 6) and compare the fifth element (1) with them.
1 is less than 2, so it should be inserted at the beginning of the sorted subarray. Shift 2, 4, and 5 to the right and insert 1: [1, 2, 4, 5, 6, 3]
Consider the first five elements as the sorted subarray (1, 2, 4, 5, 6) and compare the sixth element (3) with them.
3 is less than 4, so it should be inserted between 2 and 4. Shift 4 and 5 to the right and insert 3: [1, 2, 3, 4, 5, 6]
The array is now sorted.

In this example, the algorithm iterates over the array six times (once for each element), and it performs a maximum of five comparisons and two shifts per iteration. The total number of comparisons and shifts depends on the order of the elements in the input array.

Example

// C++ program for insertion sort

#include <bits/stdc++.h>
using namespace std;

// Function to sort an array using
// insertion sort
void insertionSort(int arr[], int n)
{
  int i, key, j;
  for (i = 1; i < n; i++)
  {
    key = arr[i];
    j = i - 1;

    // Move elements of arr[0..i-1],
    // that are greater than key, to one
    // position ahead of their
    // current position
    while (j >= 0 && arr[j] > key)
    {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

// A utility function to print an array
// of size n
void printArray(int arr[], int n)
{
  int i;
  for (i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
}

// Driver code
int main()
{
  int arr[] = {12, 11, 13, 5, 6};
  int N = sizeof(arr) / sizeof(arr[0]);

  insertionSort(arr, N);
  printArray(arr, N);

  return 0;
}

The above program will output:

5 6 11 12 13

Complexity Analysis of Insertion Sort

The time complexity of Insertion Sort is O(n^2) in the worst and average cases, and O(n) in the best case when the input array is already sorted.

In the worst case, when the input array is in reverse order, each element must be compared with all the elements in the sorted subarray, resulting in n-1 comparisons for the first element, n-2 comparisons for the second element, and so on, for a total of (n-1) + (n-2) + … + 1 = n(n-1)/2 comparisons, which is of the order of n^2. Similarly, in the average case, the number of comparisons is also proportional to n^2.

In the best case, when the input array is already sorted, each element is compared with only one or two elements in the sorted subarray before it is inserted at the correct position, resulting in a total of n-1 comparisons, which is of the order of n.

The space complexity of Insertion Sort is O(1), as it uses only a constant amount of additional memory for storing the key element and the loop variables. Therefore, Insertion Sort is efficient for small input sizes or for nearly sorted input arrays, but it is not recommended for large input sizes due to its O(n^2) time complexity.

Where is the Insertion sort algorithm used?

Insertion sort is a simple sorting algorithm that is used in various applications where the input size is small, and the array is nearly sorted. Some of the areas where Insertion sort is used are:

Small Datasets: Insertion sort is best suited for small datasets where the overhead of more complex sorting algorithms is not justified.
Online Algorithms: Insertion sort is useful for online algorithms where the data is received continuously in a stream and needs to be sorted in real-time.
Partially Sorted Data: Insertion sort performs well when the input data is partially sorted or comes in a partially sorted order.
Subroutine: Insertion sort is often used as a subroutine in more complex sorting algorithms, such as QuickSort and ShellSort.
Teaching Purposes: Insertion sort is easy to understand, simple to implement, and is often used to teach sorting algorithms in introductory computer science courses.

However, Insertion sort is not recommended for large datasets due to its quadratic time complexity. For larger datasets, more efficient algorithms like MergeSort, QuickSort, or HeapSort are used.

Advantages of Insertion Sort:

Simple and easy to understand: Insertion sort is one of the simplest sorting algorithms to understand and implement, making it useful for teaching basic sorting concepts.
Space efficient: Insertion sort requires only a constant amount of additional memory space to store the key element and the loop variables, making it space-efficient.
Efficient for small datasets: Insertion sort performs well when the dataset is small or nearly sorted, making it a good choice for sorting small lists.
Stable algorithm: Insertion sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements in the input array.

Disadvantages of Insertion Sort:

Slow for large datasets: Insertion sort has a time complexity of O(n^2), making it inefficient for large datasets, where other sorting algorithms such as MergeSort, QuickSort or HeapSort are preferred.
Not suitable for online data: Insertion sort does not perform well for online data or dynamic data, where the input array is continuously changing and sorting needs to be performed in real-time.
Not suitable for distributed data: Insertion sort is not suitable for distributed data, where data is spread across multiple nodes or processors, and sorting needs to be performed in parallel.
Performance depends on input data: The performance of Insertion sort depends on the input data, and if the input data is already sorted, Insertion sort performs well. However, if the input data is in reverse order, Insertion sort becomes inefficient.

We hope this article helped you to understand Insertion Sort Analysis in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.