#include <bits/stdc++.h>
using namespace std;

void insertion_sort(int arr[] , int n)
{
    for(int i=0;i<=n-1;i++){
        int j = i;
        
        while(j>0, arr[j-1] > arr[j])
        {
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
            
            j--;
        }
    }
}
int main() {
    
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    insertion_sort(arr, n);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    

    return 0;
}

// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
// recursive approach to reverse the linked list
Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
//this function reverse the k nodes in linked list
Node*Reversek(Node*&head,int k){
//first we have to make three node pointers

Node *prevPtr = NULL;//the prev ptr points to Null
Node *currPtr = head;//the next ptr should points toward the prev ptr because we have to reverse 
//the nodes this is possible if we point the next node towards the prev node
Node *nextptr=NULL;//we will assign the value to nextptr in the loop 
int count = 0;
while(currPtr!=NULL && count<k)
{
    nextptr = currPtr->next;
    currPtr->next = prevPtr;
    prevPtr = currPtr;
    currPtr = nextptr;
    count++;
}
if(nextptr!=NULL){
head->next = Reversek(nextptr, k);
}
return prevPtr;
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
    cout << endl;
    cout << "reversing the linked list " << endl;
    Node *NewHead = Reverse(head);
    print(NewHead);
    cout << endl;
    cout << "reversing the k nodes in linked list " << endl;
    Node *NewRev = Reversek(NewHead,2);
    print(NewRev);
}

Node*Reversek(Node*&head,int k){
//first we have to make three node pointers

Node *prevPtr = NULL;//the prev ptr points to Null
Node *currPtr = head;//the next ptr should points toward the prev ptr because we have to reverse 
//the nodes this is possible if we point the next node towards the prev node
Node *nextptr=NULL;//we will assign the value to nextptr in the loop 
int count = 0;
while(currPtr!=NULL && count<k)
{
    nextptr = currPtr->next;
    currPtr->next = prevPtr;
    prevPtr = currPtr;
    currPtr = nextptr;
    count++;
}
if(nextptr!=NULL){
head->next = Reversek(nextptr, k);
}
return prevPtr;
}

// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
// recursive approach to reverse the linked list
Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
    cout << endl;
    cout << "reversing the linked list " << endl;
    Node *NewHead = Reverse(head);

    print(NewHead);
}

Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
//in main the previous head becomes the last node
int main(){
  Node*newHead=Reverse(head);
  print(newhead);
}

// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
}

#include<iostream>
using namespace std;
struct Node {
public:
	int data;
	Node* next;
	Node(int data=0)
	{
		this->data = data;
		this->next = NULL;
	}
};
void push(Node** head_ref, int data) {
	//creating the new node and by using constructor we 
	//are storing the value of the data
	//firstly the next pointer of this new node points to NULL
	//as declared in the constructor
	//then we are pointing the pointer of this node to the new node
	//and lastly we are equating the new insert node to the previous 
	//node to connect it to the list
	Node* new_node = new Node(data);
	new_node->next =(* head_ref);
	*(head_ref) = new_node;

}
void print(Node*& head) {

	Node* temp =  head;
	while (temp != NULL)
	{
		cout << "the value of the data is " << temp->data << endl;
		temp = temp->next;
	}

}

int main() {
	Node* node;
	node = NULL;
	push(&node, 5);
	push(&node, 6);
	push(&node, 7);
	print(node);
	return 0;


}

#include<iostream>
using namespace std;
void sort(int* array, int size) {
	int key = 0, j = 0;
	for (int i = 1; i < size; i++)
	{
		key = array[i];
		j = i - 1;
		while (j >= 0 && array[j] > key)
		{
			array[j + 1] = array[j];
			j = j - 1;
		}
		array[j + 1] = key;
	}
	for (int i = 0; i < size; i++)
		cout << array[i] << "  ";
}
int main() {
	int size = 0;
	cout << "Enter size of the array " << endl;
	cin >> size;
	int* array = new int[size];
	cout << "Enter elements of the array " << endl;
	for (int i = 0; i < size; i++)
		cin >> array[i];
	sort(array, size);
}

import java.util.*;
import java.io.*;

class Solution
{
    public static void main (String[] args) 
    {
        int arr[] = new int[]{50,20,40,60,10,30};
        
        int n = arr.length;
        iSort(arr,n);
        
        for(int x:arr)
            System.out.print(x+" ");    // OUTPUT : 10 20 30 40 50 60 
        
    }
    
    static void iSort(int arr[],int n)
    {
        for(int i=1;i<n;i++){
            int key = arr[i];
            int j=i-1;
            while(j>=0 && arr[j]>key){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=key;
        }
    }
}