Java - Insertion Sort Algorithm

We have studied about searching algorithms Linear Search and Binary Search and sorting algorithm Bubble Sort in previous posts.

• Insertion sort is very simple sorting algorithm. 
• Insertion sort is good for small size collections but it is not a good algorithm for bigger size collections. 
• Insertion sort is an in-place sorting algorithm that means it uses only the given array and not required extra for temporary purpose. It only uses a constant memory space for all implementation.
• Insertion sort doesn't change the order of equal elements.

Insertion Sort -
Insertion sort simply works like we sort the playing cards. Insertion sort simply iterates through the collection once for each element and add the processed element in sorted list. It removes one element on each iteration from the given collection and put it in the correct location in the sorted collection. It process the whole collection till end and finally return the sorted collection.

Simple steps to perform bubble sort - 

• Given : An array of n elements in unsorted order.
• Required : An array of n elements in ascending order. 
• Start a loop from i= 1 to n-1 and key <- Array[i]
• Check the key with all items in sorted array Array[0--i-1] from last to first and insert the key in proper place.
• Return the sorted array.

Pseudo code (Ascending order)- 

# Input: Array elements of length n in unsorted order
# Output: Array elements of length n in ascending order

    n = length(elements)
    for i=1 to n-1

       for j = i to 1

          if elements[j] < elements[j-1] then

             swap(elements[j-1], elements[j])

          end if

       End for loop.

    End while loop.

Asymptotic Analysis of Insertion Sort Algorithm -

Best Case Scenario - If the given array or collection is already in sorted order. Best case time complexity for insertion sort is O(n).

Worst Case Scenario - If the given array or collection in reversed sorted order.  Worst case time complexity for insertion sort is О(n²).

Average-Complexity - Complexity of insertion sort algorithm is О(n²). 

Insertion Sort Implementation in Java  -

package javaprinciples.dsa;

public class InsertionSort {

public static void main(String[] args) {
int elements[] = { 4, 12, 56, 2, 7, 123, 6, 78 };

System.out.print("Input unsorted array : ");
for (int element : elements) {
System.out.print(element + " ");
}

insertionSort(elements);
System.out.print("\nOutput sorted array : ");
for (int element : elements) {
System.out.print(element + " ");
}
}

static void insertionSort(int[] elements) {
int n = elements.length;
int temp = 0;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (elements[j] < elements[j - 1]) {
temp = elements[j];
elements[j] = elements[j - 1];
elements[j - 1] = temp;
}
}
}
}
}

Output -

Input unsorted array : 4 12 56 2 7 123 6 78 
Output sorted array : 2 4 6 7 12 56 78 123 

Note - This is the simplest implementation of Insertion sort algorithm. This can be optimized to make it more faster. Try to optimize above program by yourself.

Check below links also-
Bubble Sort Algorithm analysis and implementation in Java
Linear Search Algorithm analysis and implementation in Java
Binary Search Algorithm analysis and implementation in Java
Java8 - Lambda Expressions in Java
Java8 - Default and static methods in Interface
How to create Immutable classes in JAVA
Method overloading versus method overriding in Java
Difference between Interface and Abstract class
Difference between Abstraction and Encapsulation

Difference between Comparable and Comparator in Java