# Insertion Sort Part 1 Hackerrank problem solution

## Insertion Sort – Part 1

Sorting
One 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.

Insertion Sort
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with an already sorted list.

Insert element into sorted list
Given a sorted list with an unsorted number e in the rightmost cell, can you write some simple code to insert e into the array so that it remains sorted?

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

Guideline: 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 .

Input Format
There will be two lines of input:

Size – the size of the array
Arr – the unsorted array of integers
Output Format
On each line, output the entire array every time an item is shifted in it.

Constraints
1<=Size<=1000
-10000<=e<=10000 e{Arr}

Sample Input

5
2 4 6 8 3

Sample Output

2 4 6 8 8
2 4 6 6 8
2 4 4 6 8
2 3 4 6 8

Explanation

3 is removed from the end of the array.
In the 1st line 8>3, so 8 is shifted one cell to the right.
In the 2nd line 6>3, so 6 is shifted one cell to the right.
In the 3rd line 4>3, so 4 is shifted one cell to the right.
In the 4th line 2<3, so 2 is placed at position .

Complete the method insertionSort which takes in one parameter:

Arr – an array with the value in the right-most cell.

##### Solution
``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
void print(int ar_size, int *ar)
{
for (int i = 0; i< ar_size; i++)
{
printf("%d ", ar[i]);
}
printf("\n");

}

void insertionSort(int ar_size, int *  ar)
{
int small, sorted = 1, position;
//finding the small value
for (int i = 0; i< ar_size; i++)
{
if (ar[i] > ar[i+1])
{
small = ar[i+1];
position = i;
break;
}
}

//sort the array and print
while (sorted != 0)
{

ar[position + 1] = ar[position];
print(ar_size, ar);
if (small < ar[position - 1])
{
position--;
continue;
}

ar[position] = small;
print(ar_size, ar);
sorted = 0;
}

}

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;
}
``````
``````n = int(raw_input())
test = raw_input()
a = test.split()
val = a[n-1]
for i in range(n-2,-2,-1):
test=test.split()
if i == -1:
test[i+1] = val
break
elif int(test[i])>int(val):
test[i+1]=test[i]

else:
test[i+1] = val
break
test = ' '.join(test)
print test
test = ' '.join(test)
print test

``````
```#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

void insertionSort(vector <int>  ar) {
int n = ar.size();
if(n==0)
return;
if(n==1)
cout<<ar[n-1]<<endl;
int curr = ar[n-1];
int i=n-2;
while(i>=0){
if(ar[i]>=curr){
ar[i+1]=ar[i];
}
else{
ar[i+1]=curr;
i=-1;
}
for(int j=0;j<n;j++)
cout<<ar[j]<<" ";
cout<<endl;
if(i==0){
ar[i]=curr;
for(int j=0;j<n;j++)
cout<<ar[j]<<" ";
cout<<endl;
}
i--;
}

}

/* Tail starts here */
int main() {
vector <int>  _ar;
int _ar_size;
cin >> _ar_size;
for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
int _ar_tmp;
cin >> _ar_tmp;
_ar.push_back(_ar_tmp);
}

insertionSort(_ar);

return 0;
}```
``````import java.util.Scanner;

public class Solution {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int s=scan.nextInt();
int ar[]=new int[s];
boolean check=false;
for(int i=0;i<s;i++)
{
ar[i]=scan.nextInt();
}
int var=ar[s-1];
for(int i=s-2;i>=-1;i--)
{
if(i!=-1)
{
if(var<ar[i])
{
ar[i+1]=ar[i];
}
else
{
ar[i+1]=var;
check=true;
}
}
else
{
ar=var;
}
for(int j=0;j<s;j++)
System.out.print(ar[j]+" ");
System.out.println();
if(check)
break;
}
}
}``````

### hasectic

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi