#### Sorting

Problem
Implement the Insertion sort algorithm.

Solution
This algorithm works by taking elements from an unsorted array one by one and inserting them in their proper position in the new sorted array. This invloves comparison and shifting operation.
Complexity of the algorithm is O(n2).
Consider the following array { 7, 2, 5, 3, 4 }. Let’s see how Insertion sort technique works :-

First Iteration :: { 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( 2 is placed in its proper position and 7 is shifted )

Second Iteration :: { 2, 7, 5, 3, 4 } -> { 2, 5, 7, 3, 4 } ( 5 is placed in its proper position and 7 is shifted )

Third Iteration :: { 2, 5, 7, 3, 4 } -> { 2, 3, 5, 7, 4 } ( 3 is placed in its proper position and 5 & 7 are shifted )

Fourth Iteration :: { 2, 3, 5, 7, 4 } -> { 2, 3, 4, 5, 7 } ( 4 is placed in its proper position and 5 & 7 are shifted )

```#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}

// insertion sort
void insertionSort(int arr[],int size) {
int i,j;
// select elements one by one and insert them in
// their proper position in the sorted array
for (i=1;i<size;i++) {
j = i;
// iterate and shift leftwards till we find the
// first element less than the selected element
while (j > 0 && arr[j] < arr[j-1]) {
swap(arr,j,j-1);
j--;
}
}
}

// main
int main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
insertionSort(arr,size);
cout<<"\nSorted Array   :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}```