Insertion Sort in Java | Insertion Sort Program in Java

What is Insertion Sort?

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Problem Description

Create a Java program to perform an insertion sort and further analyze its efficiency.

Insertion Sort Algorithm:

1. We will store the random set of numbers in an array.
2. We will traverse this array and insert each element of this array, to its correct position where it should actually be, by shifting the other elements on the left if required.
3. The first element in the array is considered as sorted, even if it is an unsorted array. The array is sub-divided into two parts, the first part holds the first element of the array which is considered to be sorted and second part contains all the remaining elements of array.
4. With each iteration one element from the second part is picked and inserted into the first part of array at its correct position by shifting the existing elements if required.
5. This goes until the last element in second part of array is placed in correct position in the output array.
6. Now, we have the array in sorted order.

Insertion Sort Example:

If we have the array as {50,20,60,90,40}
and we apply insertion sort to sort the array,
then the resultant array after each iteration will be as follows:

             Original array: {50, 20, 60, 90, 40}

Array after first iteration is     20 ->  50    ->  60   ->   90   ->   40
Array after second iteration is    20 ->  50    ->  60   ->   90   ->   40
Array after third iteration is     20 ->  50    ->  60   ->   90   ->   40
Array after fourth iteration is    20 ->  40    ->  50   ->   60   ->   90
            
               Sorted array is  20  40  50  60  90

Program/Source Code

Here is the source code of the Java Program to implement Insertion Sort. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/*
```

 * Java Program to Implement Insertion Sort

```
 */
```
```
 
```
```
import java.util.Scanner;
```
```
 
```
```
/* Class InsertionSort */
```
```
public class InsertionSort 
```
```
{
```
```
    /* Insertion Sort function */
```

    public static void sort( int arr[] )

```
    {
```
```
        int N = arr.length;
```
```
        int i, j, temp;
```
```
        for (i = 1; i< N; i++) 
```
```
        {
```
```
            j = i;
```
```
            temp = arr[i];    
```

            while (j > 0 && temp < arr[j-1])

```
            {
```
```
                arr[j] = arr[j-1];
```
```
                j = j-1;
```
```
            }
```
```
            arr[j] = temp;            
```
```
        }        
```
```
    }    
```
```
    /* Main method */
```

    public static void main(String[] args)

```
    {
```

        Scanner scan = new Scanner( System.in );

        System.out.println("Insertion Sort Test\n");

```
        int n, i;
```
```
        /* Accept number of elements */
```

        System.out.println("Enter number of integer elements");

```
        n = scan.nextInt();
```

        /* Create integer array on n elements */

```
        int arr[] = new int[ n ];
```
```
        /* Accept elements */
```

        System.out.println("\nEnter "+ n +" integer elements");

```
        for (i = 0; i < n; i++)
```
```
            arr[i] = scan.nextInt();
```
```
        /* Call method sort */
```
```
        sort(arr);
```
```
        /* Print sorted Array */
```

        System.out.println("\nElements after sorting ");

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

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

        System.out.println();

```
    }    
```
```
}
```

Program Explanation

1. Using a for loop, we are reading n elements from standard input into an array named arr.
2. Next, we are comparing elements of the array so that we can insert them in the proper position using the insertion sort method.
3. At the end, we are printing/displaying the sorted array.

Time Complexity: O(N)
The worst and average case time complexity of insertion sort algorithm is O(N²) while the best case time complexity of insertion sort is O(N).

Space Complexity: O(1)
The space complexity for insertion sort is O(1) if we only consider the order of space used excluding the array.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Runtime Test Cases

Testcase 1:

Insertion Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
999 921 823 816 767 712 698 657 532 412 391 323 287 256 225 162 123 64 24 6
 
Elements after sorting
6 24 64 123 162 225 256 287 323 391 412 532 657 698 712 767 816 823 921 999

Testcase 2:

Insertion Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991
 
Elements after sorting
12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991

Testcase 3:

Insertion Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
54 135 23 75 1 576 234 928 13 84 631 1283 748 124 54 6 24 485 1024 0
 
Elements after sorting
0 1 6 13 23 24 54 54 75 84 124 135 234 485 576 631 748 928 1024 1283

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

« Prev - Java Program to Implement Selection Sort

» Next - Java Program to Implement Merge Sort

Related Posts:

Recommended Articles: