# 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:

PassUnsorted listcomparisonSorted list
1{10,2,6,15,4,1}{10,2}{2,10, 6,15,4,1}
2{2,10, 6,15,4,1}{2,10, 6}{2,6, 10,15,4,1}
3{2,6, 10,15,4,1}{2,6, 10,15}{2,6, 10,15,4,1}
4 {2,6, 10,15,4,1}{2,6, 10,15,4}{2,4,6, 10,15,1}
5{2,4,6, 10,15,1}{2,4,6, 10,15,1}{1,2,4,6, 10,15}
6{}{}{1,2,4,6, 10,15}

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 2nd 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.*;
node sorted;
//define node of a linked list
class node    {
int val;
node next;
public node(int val)
{
this.val = val;
}
}
//allocate a new node
node newNode = new node(val);
}
// sort a singly linked list using insertion sort
// initially, no nodes in sorted list so its set to null
sorted = null;
// 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;
}
}

//insert a new node in sorted list
void Insert_sorted(node newNode)   {
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
}
}
}
class Main{
public static void main(String[] args)
{
//print the original list
//sort the list using insertion sort
//print the sorted list
}
} ```

Output:

1 8 32 2 10
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 {
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
// node is inserted at the beginning of the DLL
else if ((head_ref).data >= newNode.data)     {
newNode.next.prev = newNode;
}
else   {

// 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;
}
}
// sort a doubly linked list using insertion sort
// sorted doubly linked list - initially empty
Node sorted = null;
// Traverse the DLL and insert nodes to sorted list
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;
}
}

// function to print the doubly linked list
}
}

// add new node to DLL at the beginning
// 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.prev = null;
// head=>prev points to new node /
// move the head to point to the new node /

}
public static void main(String args[]) {
// create empty DLL

// add nodes to the DLL

}
}```

Output:

1 11 2 7 3 5
1 2 3 5 7 11 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.