Definition
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages like simple implementation, efficient for (quite) small data sets, more efficient in practice than most other simple quadratic algorithms, adaptive, stable, in-place; i.e., only requires a constant amount of additional memory space, online; i.e., can sort a list as it receives itInsertion Sort Example Program
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int arr1[] = new int[10];
populateArray(arr1);
System.out.println("Numbers to be sorted: ");
printArray(arr1);
insertionSort(arr1);
System.out.println("\nAfter Sorting: ");
printArray(arr1);
}
private static void insertionSort(int[] arr2) {
for (int i = 1; i < arr2.length; i++) {
int sort = arr2[i];
int j = i;
while (j > 0 && arr2[j - 1] > sort) {
arr2[j] = arr2[j - 1];
j--;
}
arr2[j] = sort;
}
}
public static void printArray(int[] arr3) {
System.out.println(Arrays.toString(arr3));
}
public static void populateArray(int[] arr3) {
for (int i = 0; i < arr3.length; i++) {
arr3[i] = (int) (Math.random() * 100);
}
}
}
Sample Output
Output is:
Numbers to be sorted:
[29, 6, 25, 7, 15, 86, 48, 78, 29, 4]
After Sorting:
[4, 6, 7, 15, 25, 29, 29, 48, 78, 86]