Insertion Sort Algorithm | Board Infinity

Introduction

In this article, we will learn about Insertion Sort. It places an unsorted element in the proper location after each iteration. Insertion sort functions similarly to how we sort the cards in our hands when playing cards. Assuming the first card is already sorted, we choose an unsorted card next. The unsorted card is positioned on the right if it is larger than the card being held on the left if not. Other unsorted cards are taken in the same manner and placed in the appropriate spot. A similar approach is used by insertion sort.

One of the simplest algorithms, with straightforward implementation, is this one. For small data values, insertion sort is generally effective. Insertion sort is adaptive in nature, so it is suitable for data sets that have already undergone some degree of sorting. Now we will be learning about its working.

In order to rank an array of size N ascendingly

Over the array, iterate from arr[1] to arr[N].
Comparing the current (key) element to the previous one.
Compare the key element to the previous elements to see if it is smaller. In order to make room for the substituted element, move the larger elements up one position.

Implementation of Insertion Sort

// 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;
}

write your code here: Coding Playground

Output

5 6 11 12 13

Time Complexity

O(N^2), Suppose, an array is in ascending order, and you want to sort it in descending order. In this case, worst case complexity occurs. Each element has to be compared with each of the other elements so, for every nth element, (n-1) number of comparisons are made.

Thus, the total number of comparisons = n*(n-1) ~ n2

Auxiliary Space

O(1), Space complexity is O(1) because an extra variable key is used.
Insertion sort is used when there are few items. It can also be helpful when the input array is nearly sorted and only a small number of the large array's elements are misplaced.

In the case of using Insertion sort for the Linked list, Below is a simple insertion sort algorithm for the linked list.

Create an empty sorted (or result) list
Traverse the given list, and do the following for every node.
Insert the current node in a sorted way in the sorted or result list.
Change the head of the given linked list to the head of the sorted (or result) list.