Java Program to perform Insertion Sort

The Insertion sort is another simple sorting algorithm, which can be used to sort any linear data structure like an array or linked list.

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

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

Time Complexity : 

Worst case performance : О(n²) comparisons, swaps
Best case performance : O(n) comparisons, O(1) swaps
Average case performance : О(n²) comparisons, swaps

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

SOURCE CODE : :

import java.util.Scanner;

public class InsertionSort {
    
    //------------------Enter data Function--------------------------------
    
    static int [] enter_data()
    {
        int i,n;
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter no. of elements u want to sort :");
        n=sc.nextInt();
        int a[]=new int[n];
        System.out.println("Enter elements--->");
        
        for(i=0;i<n;i++)
        {
            System.out.print((i+1)+" Element : ");
            a[i]=sc.nextInt();
        }
        return a;
    }

    //--------------------Insertion Sort Function-----------------------------
    
    static int [] insertionsort(int a[])
    {
        int i,j,temp,len,min;
        len=a.length;
        
        for(i=1;i<len;i++)
        {
          
            for(j=i;j>0;j--)
            { 
                if(a[j-1]>a[j])
                {
                    temp=a[j];
                    a[j]=a[j-1];
                    a[j-1]=temp;
                }
            }
        }
        
        return a;
    }
    
    //-----------------Print array---------------------------------------
    
    static void printarray(int arr[])
    {
        int i,len;
        len=arr.length;
         System.out.println("\nAfter Sorting Elements are : ");
         for(i=0;i<len;i++)
        {
            System.out.println((i+1)+" Element : "+arr[i]);
        }
    }
    
    //-----------------------Main Function-------------------------------
    
    public static void main(String[] args) {
        
        int a[],b[];
        
        a=enter_data();
        
        b=insertionsort(a);
        
        printarray(a);
       
    }
    
}

OUTPUT : :

Enter no. of elements u want to sort :10
Enter elements--->
1 Element : 4
2 Element : 1
3 Element : 5
4 Element : 8
5 Element : 2
6 Element : 9
7 Element : 3
8 Element : 4
9 Element : 1
10 Element : 0

After Sorting Elements are : 
1 Element : 0
2 Element : 1
3 Element : 1
4 Element : 2
5 Element : 3
6 Element : 4
7 Element : 4
8 Element : 5
9 Element : 8
10 Element : 9