Insertion Sort In Java – Insertion Sort Algorithm & Examples

This Tutorial Explains Insertion Sort in Java Including its Algorithm, Pseudo-code, and Examples of Sorting Arrays, Singly Linked and Doubly Linked List:

The Insertion Sort Algorithm technique is similar to Bubble sort but, is slightly more efficient. Insertion sort is more feasible and effective when a small number of elements is involved. When the data set is larger, it will take more time to sort the data.

=> Take A Look At The Java Beginners Guide Here.

Introduction To Insertion Sort In Java

In the Insertion sort technique, we assume that the first element in the list is already sorted and we begin with the second element. The second element is compared with the first and swapped if not in order. This process is repeated for all the subsequent elements.

In general, the Insertion sort technique compares each element with all of its previous elements and sorts the element to place it in its proper position.

As already mentioned, the Insertion sort technique is more feasible for a smaller set of data, and thus arrays with a small number of elements can be sorted using efficiently Insertion sort.

Insertion sort is especially useful in sorting linked list data structures. As you know, Linked lists have pointers pointing to its next element (singly linked list) and previous element (double linked list). This makes it easier to keep track of the previous and next elements.

Thus it is easier to use Insertion sort for sorting linked lists. However, sorting will take a lot of time if the data items are more.

In this tutorial, we will discuss the Insertion sort technique including its algorithm, pseudo-code, and examples. We will also implement Java programs to Sort an array, Singly linked list, and Doubly linked list using Insertion sort.

Insertion Sort Algorithm

The insertion sort algorithm is as follows.

Step 1: Repeat Steps 2 to 5 for K = 1 to N-1

Step 2: set temp = A[K]

Step 3: set J = K – 1

Step 4:

Repeat while temp <=A[J]
set A[J + 1] = A[J]
set J = J – 1
[end of inner loop]

Step 5:

set A[J + 1] = temp
[end of loop]

Step 6: exit

As you know, insertion sort starts from the second element assuming that the first element is already sorted. The above steps are repeated for all the elements in the list from the second element onwards and put in their desired positions.

Pseudocode For Insertion Sort

The pseudo-code for the insertion sort technique is given below.

procedure insertionSort(array,N )
array – array to be sorted
N- number of elements
begin
int freePosition
int insert_val

for i = 1 to N -1 do:

insert_val = array[i]
freePosition = i

//locate free position to insert the element 
while freePosition > 0 and array[freePosition -1] > insert_val do:
array [freePosition] = array [freePosition -1]
freePosition = freePosition -1
end while
//insert the number at free position
array [freePosition] = insert_val
end for
end procedure

Next, let us see an illustration that demonstrates sorting an array using Insertion sort.

Sorting An Array Using Insertion Sort

Let us take an example of Insertion sort using an array.

The array to be sorted is as follows:

Now for each pass, we compare the current element to all its previous elements. So in the first pass, we start with the second element.

Thus, we require N number of passes to completely sort an array containing N number of elements.

The above illustration can be summarized in tabular form as shown below:

As shown in the illustration above, at the end of each pass, one element goes in its proper place. Hence in general, to place N elements in their proper place, we need N-1 passes.

Insertion Sort Implementation In Java

The following program shows the implementation of the Insertion sort in Java. Here, we have an array to be sorted using the Insertion sort.

import java.util.*;
public class Main {  
public static void main(String[] args) {  
    //declare an array and print the original contents
    int[] numArray = {10,6,15,4,1,45};  
    System.out.println("Original Array:" + Arrays.toString(numArray));
    //apply insertion sort algorithm on the array
    for(int k=1; k<numArray.length-1; k++)   {  
        int temp = numArray[k];  
        int j= k-1;  
        while(j>=0 && temp <= numArray[j])   {  
            numArray[j+1] = numArray[j];   
            j = j-1;  
        }  
        numArray[j+1] = temp;  
    }  
    //print the sorted array
    System.out.println("Sorted Array:" + Arrays.toString(numArray));
}  
}  

Output:

Original Array:[10, 6, 15, 4, 1, 45]
Sorted Array:[1, 4, 6, 10, 15, 45]

In the above implementation, it is seen that sorting begins from the 2^nd element of the array (loop variable j = 1) and then the current element is compared to all its previous elements. The element is then placed in its correct position.

Insertion sort works effectively for smaller arrays and for arrays that are partially sorted where the sorting is completed in fewer passes.

Insertion sort is a stable sort i.e. it maintains the order of equal elements in the list.

Sorting A Linked List Using Insertion Sort

The following Java program shows the sorting of a singly linked list using the Insertion sort.

import java.util.*;
class Linkedlist_sort  { 
    node head; 
    node sorted; 
    //define node of a linked list
    class node    { 
        int val; 
        node next; 
        public node(int val)  
        { 
            this.val = val; 
        } 
    } 
    //add a node to the linked list
    void add(int val)  { 
        //allocate a new node
        node newNode = new node(val); 
        //link new node to list
        newNode.next = head; 
        //head points to new node
        head = newNode; 
    } 
  // sort a singly linked list using insertion sort 
    void insertion_Sort(node headref)   { 
        // initially, no nodes in sorted list so its set to null 
        sorted = null; 
        node current = headref; 
        // traverse the linked list and add sorted node to sorted list
        while (current != null)  { 
            // Store current.next in next
            node next = current.next; 
            // current node goes in sorted list 
            Insert_sorted(current); 
            // now next becomes current 
            current = next; 
        } 
        // update head to point to linked list 
        head = sorted; 
    } 

     //insert a new node in sorted list
    void Insert_sorted(node newNode)   { 
        //for head node
        if (sorted == null || sorted.val >= newNode.val)    { 
            newNode.next = sorted; 
            sorted = newNode; 
        } 
        else  { 
            node current = sorted; 
            //find the node and then insert
            while (current.next != null && current.next.val < newNode.val)   { 
                current = current.next; 
            } 
            newNode.next = current.next; 
            current.next = newNode; 
        } 
    } 
  
    //display nodes of the linked list
    void print_Llist(node head)   { 
        while (head != null)   { 
            System.out.print(head.val + " "); 
            head = head.next; 
        } 
    } 
}
class Main{
    public static void main(String[] args)  
    { 
        //define linked list object
        Linkedlist_sort list = new Linkedlist_sort(); 
        //add nodes to the list
        list.add(10); 
        list.add(2); 
        list.add(32); 
        list.add(8); 
        list.add(1); 
        //print the original list
        System.out.println("Original Linked List:"); 
        list.print_Llist(list.head); 
        //sort the list using insertion sort
        list.insertion_Sort(list.head); 
        //print the sorted list
        System.out.println("\nSorted Linked List:"); 
        list.print_Llist(list.head); 
    } 
} 

Output:

Original Linked List:
1 8 32 2 10
Sorted Linked List:
1 2 8 10 32

In the above program, we have defined a class that creates a linked list and adds nodes to it as well as sorts it. As the singly linked list has a next pointer, it is easier to keep a track of nodes when sorting the list.

Sorting A Doubly-Linked List Using Insertion Sort

The following program sorts a doubly-linked list using Insertion sort. Note that as the doubly linked list has both previous and next pointers, it is easy to update and relink the pointers while sorting the data.

class Main {
// doubly linked list node 
static class Node  {  
    int data;  
    Node prev, next;  
};  
// return a new node in DLL
static Node getNode(int data){  
    //create new node
    Node newNode = new Node(); 
    // assign data to node  
    newNode.data = data;  
    newNode.prev = newNode.next = null;  
    return newNode;  
}  
          
// insert a node in sorted DLL 
static Node insert_Sorted(Node head_ref, Node newNode)  {  
    Node current;  
      //list is empty  
    if (head_ref == null)  
        head_ref = newNode;  
      // node is inserted at the beginning of the DLL  
    else if ((head_ref).data >= newNode.data)     {  
        newNode.next = head_ref;  
        newNode.next.prev = newNode;  
        head_ref = newNode;  
    }  
    else   {  
        current = head_ref;  
  
        // find the node after which new node is to be inserted  
        while (current.next != null &&  
            current.next.data < newNode.data)  
            current = current.next;  
          //update the pointers
        newNode.next = current.next;  
          if (current.next != null)  
            newNode.next.prev = newNode;  
	current.next = newNode;  
        newNode.prev = current;  
    }  
    return head_ref; 
}  
// sort a doubly linked list using insertion sort  
static Node insertion_Sort(Node head_ref) {  
    // sorted doubly linked list - initially empty 
    Node sorted = null;  
      // Traverse the DLL and insert nodes to sorted list
    Node current = head_ref;  
    while (current != null) {
        // current.next goes into next  
        Node next = current.next;  
          // set all links to null  
        current.prev = current.next = null;  
          // current goes in sorted DLL  
        sorted=insert_Sorted(sorted, current);  
          // next now becomes current  
        current = next;  
    }  
 // Update head_ref to point to sorted doubly linked list  
    head_ref = sorted; 
    return head_ref; 
}  

 // function to print the doubly linked list  
static void print_DLL(Node head)  {  
    while (head != null)   {  
        System.out.print(head.data + " ");  
        head = head.next;  
    }  
}  
  
// add new node to DLL at the beginning 
static Node addNode(Node head_ref, int newData){  
    // create a new node 
    Node newNode = new Node();  
      // assign data
    newNode.data = newData;  
      // Make next of new node as head and previous as null  
    newNode.next = (head_ref);  
    newNode.prev = null;  
// head=>prev points to new node / 
    if ((head_ref) != null)  
        (head_ref).prev = newNode;  
      // move the head to point to the new node / 
    (head_ref) = newNode; 
      
    return head_ref; 
}  
public static void main(String args[]) {  
    // create empty DLL 
    Node head = null;  
  
    // add nodes to the DLL  
    head=addNode(head, 5);  
    head=addNode(head, 3);  
    head=addNode(head, 7);  
    head=addNode(head, 2);  
    head=addNode(head, 11);  
    head=addNode(head, 1);  
  
    System.out.println( "Original doubly linked list:");  
    print_DLL(head);  
  
    head=insertion_Sort(head);  
  
    System.out.println("\nSorted Doubly Linked List:");  
    print_DLL(head);  
  }  
}

Output:

Original doubly linked list:
1 11 2 7 3 5
Sorted Doubly Linked List:
1 2 3 5 7 11

Frequently Asked Questions

Q #1) What is Insertion Sort in Java?

Answer: Insertion sort is a simple sorting technique in Java that is efficient for a smaller data set and in place. It is assumed that the first element is always sorted and then each subsequent element is compared to all its previous elements and placed in its proper position.

Q #2) Why is Insertion Sort better?

Answer: Insertion sort is faster for smaller data sets when the other techniques like quick sort add overhead through recursive calls. Insertion sort is comparatively more stable than the other sorting algorithms and requires less memory. Insertion sort also works more efficiently when the array is almost sorted.

Q #3) What is the Insertion Sort used for?

Answer: Insertion sort is mostly used in computer applications that build complex programs like file searching, path-finding, and data compression.

Q #4) What is the efficiency of Insertion Sort?

Answer: Insertion sort has an Average case performance of O (n^2). The best case for insertion sort is when the array is already sorted and it is O (n). Worst-case performance for insertion sort is again O (n^2).

Conclusion

Insertion sort is a simple sorting technique that works on Arrays or linked lists. It is useful when the data set is smaller. As the data set gets bigger, this technique becomes slower and inefficient.

The Insertion sort is also more stable and in-place than the other sorting techniques. There is no memory overhead as no separate structure is used for storing sorted elements.

Insertion sort works well on sorting linked lists that are both singly and doubly-linked lists. This is because the linked list is made up of nodes that are connected through pointers. Hence sorting of nodes becomes easier.

In our upcoming tutorial, we will discuss yet another sorting technique in Java.

=> Read Through The Easy Java Training Series.