Insertion Sort in Java for Optimal Performance
Sorting algorithms form the foundation of many computational tasks, from organizing data to optimizing searches. Among these algorithms, Insertion Sort stands out for its simplicity and effectiveness on small datasets. While it is not the most ef...
Published
•6 min read
T
I am Tuanh.net. As of 2024, I have accumulated 8 years of experience in backend programming. I am delighted to connect and share my knowledge with everyone.
1. What Is Insertion Sort?
Insertion Sort is a comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by taking elements from an unsorted list and inserting them into their correct position within a sorted subset. The approach mimics how we sort playing cards in our hands — by placing each card in its correct position relative to the others.
1.1 How It Works
The algorithm divides the array into two sections:
- Sorted Section: Starts with the first element.
- Unsorted Section: All other elements.
For each element in the unsorted section, it finds the appropriate position in the sorted section and shifts the elements to accommodate it.
1.2 Code Example: Basic Insertion Sort
Below is a Java implementation of the Insertion Sort algorithm:
public class InsertionSortExample {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; 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--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] data = {9, 5, 1, 4, 3};
System.out.println("Unsorted Array:");
for (int num : data) {
System.out.print(num + " ");
}
insertionSort(data);
System.out.println(" Sorted Array:");
for (int num : data) {
System.out.print(num + " ");
}
}
}
Explanation:
- The insertionSort method starts from the second element (index = 1) because the first element is trivially sorted.
- It selects the current element (key) and compares it with the sorted portion on its left.
- Elements larger than key are shifted one position to the right, creating a space for the key to be inserted.
1.3 Output of the Example
For the input {9, 5, 1, 4, 3}, the output will be:
Unsorted Array:
9 5 1 4 3
Sorted Array:
1 3 4 5 9
Explanation:
- The insertionSort method starts from the second element (index = 1) because the first element is trivially sorted.
- It selects the current element (key) and compares it with the sorted portion on its left.
- Elements larger than key are shifted one position to the right, creating a space for the key to be inserted.
1.3 Output of the Example
For the input {9, 5, 1, 4, 3}, the output will be:
Unsorted Array:
9 5 1 4 3
Sorted Array:
1 3 4 5 9
2. Analyzing Insertion Sort
2.1 Time Complexity
Insertion Sort has three scenarios to consider:
- Best Case (O(n)): When the array is already sorted, the algorithm only performs n comparisons.
- Worst Case (O(n^2)): When the array is sorted in reverse order, the algorithm performs the maximum number of comparisons and shifts.
- Average Case (O(n^2)): On average, half of the elements are compared and shifted for each insertion.
2.2 Space Complexity
Insertion Sort is an in-place algorithm, meaning it does not require additional memory for operations. Its space complexity is O(1).
2.3 Stability of the Algorithm
Insertion Sort is stable because it does not swap equal elements unnecessarily. This is crucial in cases where data has secondary sorting criteria.
3. Optimizations and Use Cases
3.1 Optimization for Binary Insertion Sort
One way to improve Insertion Sort is by using a binary search to find the correct position for the key. This reduces the comparisons to O(log n) while maintaining the overall time complexity as O(n^2) due to the shifts.
public class OptimizedInsertionSort {
public static void insertionSortWithBinarySearch(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int left = 0;
int right = i - 1;
// Perform binary search to find the correct position
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Shift elements to make space for the key
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
public static void main(String[] args) {
int[] data = {10, 7, 3, 2, 8, 1};
System.out.println("Unsorted Array:");
for (int num : data) {
System.out.print(num + " ");
}
insertionSortWithBinarySearch(data);
System.out.println(" Sorted Array:");
for (int num : data) {
System.out.print(num + " ");
}
}
}
3.2 When to Use Insertion Sort
- Small Datasets: Insertion Sort excels on small arrays due to its low overhead.
- Nearly Sorted Data: If the data is nearly sorted, Insertion Sort performs close to O(n) time complexity.
- Real-Time Systems: With minimal space requirements and predictable behavior, it's suitable for systems with tight constraints.
3.3 Advantages and Disadvantages
Advantages:
- Simple to implement.
- Efficient for small or nearly sorted datasets.
- Stable sorting algorithm.
Disadvantages:
- Not efficient for large datasets due to O(n^2) complexity.
- Requires significant element shifts.
4. Extending Insertion Sort
4.1 Recursive Insertion Sort
For academic purposes, Insertion Sort can also be implemented recursively:
public class RecursiveInsertionSort {
public static void recursiveSort(int[] arr, int n) {
if (n <= 1) return;
// Sort first n-1 elements
recursiveSort(arr, n - 1);
// Insert last element into sorted part
int last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
public static void main(String[] args) {
int[] data = {4, 3, 2, 10, 12, 1, 5};
System.out.println("Unsorted Array:");
for (int num : data) {
System.out.print(num + " ");
}
recursiveSort(data, data.length);
System.out.println(" Sorted Array:");
for (int num : data) {
System.out.print(num + " ");
}
}
}
5. Conclusion
Insertion Sort is a fundamental algorithm that serves as an excellent starting point for understanding sorting techniques. While not the fastest, its stability and simplicity make it a go-to choice for small or nearly sorted datasets. For larger datasets, optimized variants like Binary Insertion Sort can improve performance.
Do you have any questions about Insertion Sort or other algorithms? Let’s discuss them in the comments below!
Read more at : Insertion Sort in Java for Optimal Performance
