# Insertion Sort

QUESTION

Sort the given set of numbers using Insertion Sort. The first line of the input contains the number of elements, the second line of the input contains the numbers to be sorted. In the output print the status of the array and all the iteration and the final sorted array in the given format.

“TESTCASE_1”: “8\n76 15 0 70 65 46 23 78\n###—###SEPERATOR—###—\n15 76 0 70 65 46 23 78 \n0 15 76 70 65 46 23 78 \n0 15 70 76 65 46 23 78 \n0 15 65 70 76 46 23 78 \n0 15 46 65 70 76 23 78 \n0 15 23 46 65 70 76 78 \n0 15 23 46 65 70 76 78 \nSorted Array:0 15 23 46 65 70 76 78 “, “TESTCASE_2”: “5\n64 25 22 90 35\n###—###SEPERATOR—###—\n25 64 22 90 35 \n22 25 64 90 35 \n22 25 64 90 35 \n22 25 35 64 90 \nSorted Array:22 25 35 64 90”, “TESTCASE_3”: “9\n99 88 77 66 55 44 33 22 11\n###—###SEPERATOR—###—\n88 99 77 66 55 44 33 22 11 \n77 88 99 66 55 44 33 22 11 \n66 77 88 99 55 44 33 22 11 \n55 66 77 88 99 44 33 22 11 \n44 55 66 77 88 99 33 22 11 \n33 44 55 66 77 88 99 22 11 \n22 33 44 55 66 77 88 99 11 \n11 22 33 44 55 66 77 88 99 \nSorted Array:11 22 33 44 55 66 77 88 99 “, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````#include <stdio.h>
#include <math.h>
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;

while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
printArray(arr, n);
}
}

int main()
{
int n,i;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
insertionSort(arr, n);
printf("Sorted Array:");
printArray(arr, n);

return 0;
}``````