# Programming Videos

## Search

### Insertion Sort Program in Java with Explanation

Write a program to implement insertion sort algorithm in java.  How insertion sort is different from bubble sort and selection sort.

Insertion sort is a simple sorting algorithm. It works by inserting each element at the proper place in a sorted list.

Insertion sort explanation.

Java programs

## Insertion Sort Program in Java

```package insertionsort;

import java.util.*;

public class Insertionsort {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {

int n;

System.out.println("Enter the number of element in an array");

Scanner in = new Scanner(System.in);
n = in.nextInt();

int[] arr = new int[n];

System.out.println("Enter unsorted values in an array");

int i, j ,k;

/* Taking unsorted values from user */

for (i = 0 ; i < n; i++) {

arr[i] = in.nextInt();

}

/* Sorting values using insertion sort */

for ( i = 1; i < n; i++) {

k = arr[i];

for (j = i - 1; j >= 0 && k < arr[j]; j-- ) {

arr[j+1] = arr[j];
}

arr[j+1] = k;
}

System.out.println ("After sorting an array");

for (j = 0; j < n; j++) {

System.out.print(arr[j]+" ");
}
}

}

```

Output -

Enter the number of element in an array  :  4

Enter unsorted values in an array :

12
5
9
2

After sorting an array :

2     5      9      12

Explanation

Suppose we have input following values.

12   5   9    2

Step 1 -  12 is compared with 5 and position is swapped.

After step 1 -    5   12  9   2

Step 2 - 9 is compared with 5 and 12 and position is swapped.

After step 2 -   5    9    12    2

Step 3 - 2 is compared with 5, 9 and 12 and position is swapped.

After step 3 -   2    5    9    12

You can also create separate method for insertion sort and sort the unsorted array. Here is the code snippet for sorting.

```public static void insertionSort(int[] A){

for(int i = 1; i < A.length; i++) {

int value = A[i];
int j = i - 1;

while(j >= 0 && A[j] > value){

A[j + 1] = A[j];
j = j - 1;

}

A[j + 1] = value;

}

/* Assume this is the method which prints
the final sorted array */

printArray(A);
}

```