# 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.

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

First step resulted array is above.

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

Resulted array is as shown above.

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

Resulted array is as shown above.

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

Resulted array is as shown above.

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

Resulted array is as shown above.

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

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!.