Insertion Sort in Java efficiently sorts a small number of elements or partially sorted arrays. It works by iteratively inserting elements into their correct positions within a sorted subarray. In this article, we will explore how to implement and use Insertion Sort in Java.
Algorithm Steps:
- Start by considering the first element as a sorted subarray.
- Iterate through the remaining elements, starting from the second element.
- Compare each element with the elements in the sorted subarray, moving them to the right until finding the correct position for insertion.
- Insert the element into its correct position within the sorted subarray.
- Repeat steps 2 to 4 until all elements are inserted and the array is sorted.
Java Implementation
import java.util.*;
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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) {
int[] arr = {5, 2, 8, 12, 3};
System.out.println("Original Array: " + Arrays.toString(arr));
insertionSort(arr);
System.out.println("Sorted Array: " + Arrays.toString(arr));
}
}
Output
Original Array: [5, 2, 8, 12, 3]
Sorted Array: [2, 3, 5, 8, 12]Time Complexity: The time complexity of Insertion Sort in the worst case scenario is O(n^2), where n is the number of elements in the array. This occurs when the array is sorted in reverse order. In the best case scenario, when the array is already sorted, the time complexity reduces to O(n).
Space Complexity: The space complexity of Insertion Sort is O(1) because the algorithm sorts the elements in-place, without requiring additional space proportional to the input size.
Conclusion: Insertion Sort in Java
In conclusion, understanding the implementation and performance characteristics of Insertion Sort in Java can help you make informed decisions when choosing the appropriate sorting algorithm for your specific needs.
Related Articles: