Table of Contents ๐
- Introduction to Insertion Sort
- How Does Insertion Sort Work?
- Java Implementation
- Time and Space Complexity
- Conclusion
๐ Introduction to Insertion Sort
Insertion sort is a simple yet powerful sorting algorithm that is intuitive and easy to implement. It’s particularly useful for sorting small arrays and for nearly sorted arrays. Let’s dive in!
๐จ How Does Insertion Sort Work?
Imagine you’re playing a game of cards. When you’re dealt cards, you likely sort them in your hand, inserting each new card into its proper place. That’s exactly how Insertion Sort works.
Hereโs how it works with an array [4, 3, 2, 10, 12, 1, 5, 6]:
- Start from the second element (assume the first element is sorted)
- Compare the second element with the first one and insert it in the correct position, just like you’d arrange your cards.
- Continue this process for all elements.
Letโs illustrate:
- First Iteration:
[4, 3, 2, 10, 12, 1, 5, 6] (4 is considered sorted) - Second Iteration:
[3, 4, 2, 10, 12, 1, 5, 6] (3 is inserted before 4) - Third Iteration:
[2, 3, 4, 10, 12, 1, 5, 6] (2 is inserted at the beginning) - And so on…
๐ป Implementation of Insertion Sort in Java
Here is a complete Java implementation of the Insertion Sort algorithm:
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
insertionSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
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 = j - 1;
}
arr[j + 1] = key;
}
}
}
๐ Time and Space Complexity of Insertion Sort
- Time Complexity:
- Best-case: O(n) when the array is already sorted.
- Average and Worst-case: O(n2)
- Space Complexity: The algorithm runs in constant extra space O(1).
๐ Conclusion
That’s Insertion Sort for youโa simple and intuitive algorithm. While not suitable for large datasets due to its O(n2) complexity, it works well for small or nearly sorted arrays.
If you found this guide helpful, please share with your friends, and spread the knowledge!