Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works by repeatedly taking the next element from the unsorted part of the array and inserting it into its correct position in the sorted part of the array. This process continues until all elements are sorted.
Here’s a step-by-step explanation of the insertion sort algorithm:
1. Start with the second element (index 1) and compare it with the first element (index 0).
2. If the second element is smaller, swap it with the first element.
3. Move to the third element (index 2) and insert it into its correct position among the first three elements.
4. Repeat this process for each subsequent element until the entire array is sorted.
Now, let’s see an implementation of insertion sort in Java:
public class InsertionSort {
public static void insertionSort(int[] array) {
int n = array.length;
for (int i = 1; i < n; i++) {
int key = array[i];
int j = i - 1;
// Move elements of array[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
This Java program demonstrates the insertion sort algorithm. The `insertionSort` method sorts an array of integers in ascending order. The `main` method initializes an array with some unsorted elements, calls the `insertionSort` method to sort the array, and then prints the sorted array.
The time complexity of insertion sort is O(n^2) in the worst-case scenario, where n is the number of elements in the array. However, it can be efficient for small datasets or nearly sorted arrays due to its simplicity and adaptive nature.