In this article, we will discuss what is insertion sort, how it works? and how to implement it using Java.
What is Insertion Sort Algorithm?
Insertion sort is a simple and efficient comparison sort. In this algorithm, each iteration removes an element from the input data and inserts it into the correct position in the list is sorted. The choice of the element is removed from the input is random and this process is repeated until all input elements have gone through.
Advantages
- Efficient for small data
- Adaptive: If the input list is presorted [may not be complete] then insertions sort takes O(n + d), where d is the number of inversions
- Practically more efficient than selection and bubble sorts, even though all of them have O(n2) worst case complexity
- Stable: Maintains relative order of input data if the keys are same
- In-place: It requires only a constant amount O(1) of additional memory space
- Online: Insertion sort can sort the list as it receives it
How Insertion Sort Works?
Let's understand how insertion sort works with a simple example.
Step 1: Let's we have input as integer array:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
Step 2: For i = 1, since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
Step 3: For i = 2, 13 will remain at its position as all elements in A[0..i-1] are smaller than 13
11, 12, 13, 5, 6
Step 4: For i = 3, 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
Step 5: For i = 4, 6 will move to a position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
Let's look at the source so that we can understand this flow easily.
Insertion Sort Implementation in Java
import java.util.Arrays;
/**
* Class demonstrate the Insertion sort algorithm
* @author Ramesh Fadatare
*
*/
public class InsertionSort {
/* Function to sort array using insertion sort */
private void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/*
* Move elements of arr[0..i-1], that are greater than key, to one
* position ahead of their current position
*/
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String args[]) {
InsertionSort insertionSort = new InsertionSort();
int arr[] = { 20, 10, 5, 6, 2, 3, 4 };
System.out.println("Before Sorting an array : " + Arrays.toString(arr));
insertionSort.insertionSort(arr);
System.out.println("After Sorting an array : " + Arrays.toString(arr));
}
}
Output:
Before Sorting an array : [20, 10, 5, 6, 2, 3, 4]
After Sorting an array : [2, 3, 4, 5, 6, 10, 20]Generic Implementation
Let's create a generic implementation of the Insertion Sort algorithm so that we can sorting Integer, String, Double etc. Sorts according to the natural ordering of its elements. Wrapper classes and String internally implement the Comparable interface.
This program demonstrates sorting Integer and String array using Insertion Sort Algorithm.
import java.util.Arrays;
/**
* Insertion sort is a simple sorting algorithm: a comparison sort in which the
* sorted array (or list) is built one entry at a time. It is much less
* efficient on large lists than more advanced algorithms such as quicksort,
* heapsort, or merge sort.
*
* @author Ramesh Fadatare
*/
public class InsertionSort<T extends Comparable<T>> {
private InsertionSort() {
}
public static <T extends Comparable<T>> T[] sort(T[] unsorted) {
int length = unsorted.length;
for (int i = 1; i < length; i++) {
sort(i, unsorted);
}
return unsorted;
}
private static <T extends Comparable<T>> void sort(int i, T[] unsorted) {
for (int j = i; j > 0; j--) {
T jthElement = unsorted[j];
T jMinusOneElement = unsorted[j - 1];
if (jthElement.compareTo(jMinusOneElement) < 0) {
unsorted[j - 1] = jthElement;
unsorted[j] = jMinusOneElement;
} else {
break;
}
}
}
public static void main(String[] args) {
Integer arr[] = { 20, 10, 5, 6, 2, 3, 4 };
System.out.println("--------Sorting integer array using insertion sort algorithm--------");
System.out.println();
System.out.println("Before Sorting an array : " + Arrays.toString(arr));
InsertionSort.sort(arr);
System.out.println("After Sorting an array : " + Arrays.toString(arr));
System.out.println();
System.out.println("--------Sorting String array using insertion sort algorithm--------");
System.out.println();
String[] stringArray = { "c", "a", "e", "b", "d" };
System.out.println("Before sorting the array elements : " + Arrays.toString(stringArray));
InsertionSort.sort(stringArray);
System.out.println("After sorting the array elements : " + Arrays.toString(stringArray));
}
}
Output:
--------Sorting integer array using insertion sort algorithm--------
Before Sorting an array : [20, 10, 5, 6, 2, 3, 4]
After Sorting an array : [2, 3, 4, 5, 6, 10, 20]
--------Sorting String array using insertion sort algorithm--------
Before sorting the array elements : [c, a, e, b, d]
After sorting the array elements : [a, b, c, d, e]Performance
If every element is greater than or equal to every element to its left, the running time of insertion sort is Θ(n). This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.
- Worst case complexity: Θ(n2)
- Best case complexity: Θ(n)
- Average case complexity: Θ(n2)
- Worst case space complexity: O(n2) total, O(1) auxiliary
Comments
Post a Comment
Leave Comment