In this article, we will discuss the simple sorting algorithm called insertion sort.
What is insertion sort?
This works in a similar fashion as playing a deck of cards. Assuming two different parts – sorted and unsorted, we need to pick and sort each card from an unsorted part into a sorted part.
Steps to be folowed
The first element in an array is to be considered as already sorted.
The next element is to be taken and compared with the elements in a sorted array.
Insert the element by shifting the elements in the sorted array which are greater than the value to be sorted
Example
import java.util.Arrays;
public class InsertionSort {
private void sortArray(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
InsertionSort insertionSort = new InsertionSort();
int[] arr = { 2, 7, 5, 8, 3, 4, 1, 6 };
insertionSort.sortArray(arr);
System.out.println(Arrays.toString(arr));
}
}Output
[1, 2, 3, 4, 5, 6, 7, 8]