## Q. Write a program to sort an array element in ascending order using Insertion Sort Algorithm.

Insertion Sort :- Insertion sort is a simple sorting algorithm that works out how to sort cards playing in our hands.

Ascending Order :- Numbers are said to be in ascending order when they are arranged from smallest to largest number. Such as 5, 9, 13, 17 and 21 are arranged in ascending order.

## Insertion Sort Algorithm

```START
Step 1 : If it is the first element, it is already sorted. return 1;
Step 2 : Pick next element
Step 3 : Compare with all elements in the sorted sub-list
Step 4 : Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 : Insert the value
Step 6 : Repeat until list is sorted
STOP
```

# Insertion Sort Program

• C
• C++
• Java
• Python
• C#
• PHP
• ```// Insertion sort in C
#include <stdio.h>
void print_array(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void insertion_sort(int arr[], int size)
{
for (int step = 1; step < size; step++)
{
int key = arr[step];
int j = step - 1;
while (key < arr[j] && j >= 0)
{
// For descending order, change key< arr[j] to key>arr[j].
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main()
{
int arr[] = {15, 50, -27, -4, 10};
int size = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, size);
printf("Sorted array in ascending order:\n");
print_array(arr, size);
}
```
```// Insertion sort in C++
#include <iostream>
using namespace std;
void print_array(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void insertion_sort(int arr[], int size)
{
for (int step = 1; step < size; step++)
{
int key = arr[step];
int j = step - 1;
while (key < arr[j] && j >= 0)
{
// For descending order, change key< arr[j] to key>arr[j].
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main()
{
int arr[] = {15, 50, -27, -4, 10};
int size = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, size);
cout << "Sorted array in ascending order:\n";
print_array(arr, size);
}
```
```// Insertion sort in Java
import java.util.Arrays;
class LFC {
void insertion_sort(int arr[]) {
int size = arr.length;
for (int step = 1; step < size; step++) {
int key = arr[step];
int j = step - 1;
while (j >= 0 && key < arr[j]) {
// For descending order, change key< arr[j] to key>arr[j].
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
public static void main(String args[]) {
int[] arr = { 15, 50, -27, -4, 10 };
LFC is = new LFC();
is.insertion_sort(arr);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(arr));
}
}
```
```# Insertion sort in Python
def insertion_sort(arr):
for step in range(1, len(arr)):
key = arr[step]
j = step - 1
while j >= 0 and key < arr[j]:
# For descending order, change key< arr[j] to key >arr[j].
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
arr = [15, 50, -27, -4, 10 ]
insertion_sort(arr)
print('Sorted Array in Ascending Order:')
print(arr)
```
```using System;
namespace InsertionSortDemo {
class LFC {
static void Main(string[] args) {
int[] arr = new int[5] { 15, 50, -27, -4, 10  };
int n = 5, i, j, val, flag;
for (i = 1; i < n; i++) {
val = arr[i];
flag = 0;
for (j = i - 1; j >= 0 && flag != 1; ) {
if (val < arr[j]) {
arr[j + 1] = arr[j];
j--;
arr[j + 1] = val;
}
else flag = 1;
}
}
Console.Write("Sorted Array in Ascending Order: \n");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}
```
```\$arr = array(15, 50, -27, -4, 10);
function insertion_sort(\$arr)
{
for (\$i = 0; \$i < count(\$arr); \$i++) {
\$val = \$arr[\$i];
\$j = \$i-1;
while(\$j>=0 && \$arr[\$j] > \$val){
\$arr[\$j+1] = \$arr[\$j];
\$j--;
}
\$arr[\$j+1] = \$val;
}
return \$arr;
}
\$sorted_arr = insertion_sort(\$arr);
echo "Sorted Array in Ascending Order: \n";
for(\$i = 0; \$i < 5; \$i++)
echo \$sorted_arr[\$i]." ";
```
```// Insertion sort in C
#include <stdio.h>
void print_array(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void insertion_sort(int arr[], int size)
{
for (int step = 1; step < size; step++)
{
int key = arr[step];
int j = step - 1;
while (key < arr[j] && j >= 0)
{
// For descending order, change key< arr[j] to key>arr[j].
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main()
{
int arr[] = {15, 50, -27, -4, 10};
int size = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, size);
printf("Sorted array in ascending order:\n");
print_array(arr, size);
}
```

#### Output

```Sorted array in ascending order:
-27 -4 10 15 50
```

## Recommended Programs

Insertion Sort In Descending Order
Finding Largest Element In An Array