Insertion Sort

Given an array of numbers aim is to sort those numbers in ascending/descending order using the Insertion Sort algorithm.

Insertion Sort is a type of sorting algorithm where it starts with two numbers initially and makes them sort by moving all greater elements that the last element to the right side. By doing this for all the N iterations will give us a sorted array. Let us consider the below input and algorithm expected output.

Input: {10, 30, 14, -9, 21, -12, 5}
Output: {-12, -9, 5, 10, 14, 21, 30}
The above output is in ascending sorted order.

Step by step approach

For better understanding please check below illustration of the algorithm.

103014-921-125

As 10 < 30, No need to move element to right side.

103014-921-125

First step resulted array is above.

103014-921-125

As 30 > 14, we need to move that to right side of 14.

101430-921-125

Resulted array is as shown above.

101430-921-125

As -9 is lesser than all 3 elements before it, so need to move all 3 elements to right side of -9.

-910143021-125

Resulted array is as shown above.

-910143021-125

As 21 < 30, element 30 moved to right side of 21.

-910142130-125

Resulted array is as shown above.

-910142130-125

As -12 is lesser than all elements before it, so need to move all elements to right side of -12.

-12-9101421305

Resulted array is as shown above.

-12-9101421305

As 5 is lesser than all elements until 10, so those elements move to right side of 5.

-12-9510142130

Resulted sorted array is as shown above.

As per above illustration, sorting will be happen in N iterations with each iteration has N possible swaps(worst case). Lets jump into code for the insertion sort algorithm.

“C” code

#include <iostream>

using namespace std;

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void printArray(int inp[], int len)
{
	for(int i=0; i<len; i++)
	{
		cout<<inp[i]<<" ";
	}
	cout<<endl;
}

void insertionSort(int inp[], int len)
{
	for(int i=1; i<len; i++)
	{
		int curIdx = i;
	 	while(inp[curIdx] < inp[curIdx-1])
		{
			swap(inp[curIdx], inp[curIdx-1]);
			--curIdx;
			if(curIdx == 0) break;
		}
	}
}

int main(int argc, char* argv[])
{
	int inp[] = {10, 30, 14, -9, 21, -12, 5};
	int len = sizeof(inp) / sizeof(inp[0]);

	cout<<"Input Array: "<<endl;
	printArray(inp, len);
	insertionSort(inp, len);
	cout<<endl<<"Sorted Array: "<<endl;
	printArray(inp, len);
	return 0;
}
Output:
Input Array:
10 30 14 -9 21 -12 5
Sorted Array:
-12 -9 5 10 14 21 30

Complexity: O(n^2)Space: O(n)

This is it for the Insertion Sort algorithm. If there are any errors observed in algorithm or coding, please let readers know by commenting on those below, Cheers!.

Advertisements