Welcome to our in-depth guide on Java Insertion Sort! This tutorial is perfect for beginners and intermediates looking to understand and implement the Insertion Sort algorithm in Java. Let's dive right in!
Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It's named "Insertion Sort" because each element (except the first) is inserted in its correct position within the already sorted part of the array.
Insertion Sort is ideal for small arrays and lists that are nearly sorted. It's easy to understand and implement, making it a great choice for teaching the fundamentals of sorting algorithms.
Let's create a simple Insertion Sort implementation in Java.
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {20, 35, -15, 7, 55, 1, -27, 3};
insertionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
📝 Note: We start from the second element to avoid swapping with itself.
int key = arr[i];
💡 Pro Tip: We'll store the current element as 'key'.
int j = i - 1;
💡 Pro Tip: We'll start from the previous element and move towards the left.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
💡 Pro Tip: If the current element (key) is smaller than the element at the current position (j), we swap them and move one position to the left.
arr[j + 1] = key;
}
}
}Insertion Sort can be used in applications that require sorting small datasets or in situations where the data is initially sorted or nearly sorted. Examples include sorting user input, parsing log files, and managing in-memory data structures.
Which part of the Insertion Sort algorithm handles the insertion of elements one by one in their correct position?