# Insertion sort

QUESTION

Sorting \nOne common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.\n\nInsertion Sort \nThese challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with an already sorted list.\n\nInsert element into sorted list \n\nGiven a sorted list with an unsorted number in the rightmost cell, can you write some simple code to insert into the array so that it remains sorted?\n\nPrint the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.\n\nGuideline: You can copy the value of e to a variable and consider its cell \”empty\”. Since this leaves an extra cell empty on the right, you can shift everything over until v can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with e .\n\nInput Format \n\nThere will be two lines of input:\nsize – the size of the array\nArr – the unsorted array of integers\n\nOutput Format \nOn each line, output the entire array every time an item is shifted in it.\n\nConstraints \n\n1<=size<=1000 \n-10000<=e<=10000, e belongs to arr.

``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

void insertionSort(int ar_size, int *  ar)
{
int i,j,k,m;
for(i=1;i<ar_size;i++)
{
for(j=0;j<i;j++)
{
if(ar[i]<ar[j])
{
ar[i] = ar[i] + ar[j];
ar[j] = ar[i] - ar[j];
ar[i] = ar[i] - ar[j];
}
}
for(j=0;j<ar_size;j++)
{
printf("%d ",ar[j]);
}
printf("\n");
}
}
int main(void)
{
int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++)
{
scanf("%d", &_ar[_ar_i]);
}
insertionSort(_ar_size, _ar);
return 0;
}  