# Insertion Sort - Part 1

### Problem Statement :

```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 a nearly sorted list.

Insert element into sorted list
Given 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?

Since this is a learning exercise, it won't be the most efficient way of performing the insertion. It will instead demonstrate the brute-force method in detail.

Function Description

Complete the insertionSort1 function in the editor below.

insertionSort1 has the following parameter(s):

n: an integer, the size of arr
arr: an array of integers to sort

Returns

None: Print the interim and final arrays, each on a new line. No return value is expected.

Input Format

The first line contains the integer n, the size of the array arr.
The next line contains n space-separated integers arr  . . . arr[ n - 1 ] .

Constraints

1  <=  n  <=  1000
-10000 <=  arr[ i ]  <=  10000

Output Format

Print the array as a row of space-separated integers each time there is a shift or insertion.```

### Solution :

```                            ```Solution in C :

In  C++  :

#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--;
}

}

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;
}

In   Java  :

import java.util.Scanner;

public class Solution {

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;
}
}
}

In   C   :

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

void insertionSort(int ar_size, int *  ar) {
int v;
int idx;
int i;
int done = 0;

v = ar[ar_size - 1];

for (idx = ar_size-2; idx >= 0; idx--) {
if (v > ar[idx]) {
ar[idx+1] = v;
done = 1;
} else {
ar[idx+1] = ar[idx];
}
for (i = 0; i < ar_size; i++)
printf("%d ", ar[i]);
printf("\n");

if (done)
break;
}

if (!done) {
ar = v;
for (i = 0; i < ar_size; i++)
printf("%d ", ar[i]);
printf("\n");
}

}

/* Tail starts here */
int main() {

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;
}

In   Python3  :

n = int(input())
d = [int(x) for x in input().split()]
t = d[n-1]
k = n-2
while k >= 0 and t < d[k]:
d[k+1] = d[k]
s = str(d)[1:-1].replace(",", "")
print(s)
k -= 1
d[k+1] = t
s = str(d)[1:-1].replace(",", "")
print(s)```
```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element