Insertion Sort

Table of Contents 📚

1. Introduction to Insertion Sort
2. How Does Insertion Sort Work?
3. Java Implementation
4. Time and Space Complexity
5. 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]:

1. Start from the second element (assume the first element is sorted)
2. Compare the second element with the first one and insert it in the correct position, just like you’d arrange your cards.
3. 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(n²)
• 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(n²) 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!