Insertion Sort - potatoscript/dsa GitHub Wiki

🧩 Insertion Sort – One by One Organizer

Insertion Sort is a simple sorting algorithm that works similarly to how you might sort playing cards in your hands. As you go through the list of items, you pick one item at a time and place it in its correct position within the already sorted portion of the list. It's like having a sorted pile of cards and inserting each new card into its correct position, shifting the other cards accordingly.

While Insertion Sort is simple and intuitive, it is not the most efficient algorithm for large datasets. However, it works well for small or nearly sorted arrays and is commonly used in situations where the data is already mostly sorted.

---

📖 How Does Insertion Sort Work?

Step-by-Step Explanation:

1. Start with the second element in the array. (The first element is already considered "sorted.")
2. Compare this element with the one before it.
3. If the element is smaller, shift the larger elements to the right to make space for the current element.
4. Insert the current element into the correct position in the sorted portion of the array.
5. Move on to the next element and repeat until the entire array is sorted.

---

🚀 Example of Insertion Sort

Let’s take an unsorted array to demonstrate how Insertion Sort works:

[5, 2, 9, 1, 5, 6]

Step-by-Step Walkthrough:

1. First pass:

   • Start with the second element, 2 (index 1).
   • Compare 2 with 5 (index 0).
   • Since 2 is smaller, shift 5 to the right.
   • Insert 2 in the first position.
   • Array becomes: [2, 5, 9, 1, 5, 6]

2. Second pass:

   • Now, consider 9 (index 2).
   • Compare 9 with 5 (index 1). Since 9 is larger, no shift is needed.
   • Array remains: [2, 5, 9, 1, 5, 6]

3. Third pass:

   • Now, consider 1 (index 3).
   • Compare 1 with 9 (index 2), and shift 9 to the right.
   • Compare 1 with 5 (index 1), and shift 5 to the right.
   • Compare 1 with 2 (index 0), and shift 2 to the right.
   • Insert 1 in the first position.
   • Array becomes: [1, 2, 5, 9, 5, 6]

4. Fourth pass:

   • Now, consider 5 (index 4).
   • Compare 5 with 9 (index 3), and shift 9 to the right.
   • Compare 5 with 5 (index 2), no shift needed.
   • Insert 5 in its correct position (index 3).
   • Array becomes: [1, 2, 5, 5, 9, 6]

5. Fifth pass:

   • Now, consider 6 (index 5).
   • Compare 6 with 9 (index 4), and shift 9 to the right.
   • Compare 6 with 5 (index 3), no shift needed.
   • Insert 6 in the correct position (index 4).
   • Array becomes: [1, 2, 5, 5, 6, 9]

The final sorted array is:

[1, 2, 5, 5, 6, 9]

---

🧑‍💻 C# Code for Insertion Sort

Here is the C# implementation of Insertion Sort:

using System;

public class InsertionSortExample
{
    // Method for Insertion Sort
    public static void InsertionSort(int[] arr)
    {
        int n = arr.Length;
        
        // Loop through each element starting from the second one
        for (int i = 1; i < n; i++)
        {
            int current = arr[i]; // The element to be inserted
            int j = i - 1;

            // Shift elements to the right to make space for the current element
            while (j >= 0 && arr[j] > current)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert the current element into its correct position
            arr[j + 1] = current;
        }
    }

    // Main method to run and test Insertion Sort
    public static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 5, 6 };
        
        Console.WriteLine("Unsorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
        
        // Call the InsertionSort method
        InsertionSort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
    }
}

🧑‍💻 Explanation of Code:

1. The method InsertionSort takes an integer array as input.
2. The outer loop starts at the second element (index 1) since the first element is already "sorted".
3. The inner while loop shifts elements that are larger than the current element to the right.
4. Once the correct position is found, the current element is placed there.

🧑‍💻 Output:

When you run the code, the output will look like this:

Unsorted array:
5 2 9 1 5 6 

Sorted array:
1 2 5 5 6 9 

---

📊 Time Complexity of Insertion Sort

• Best Case: O(n) – The best case happens when the array is already sorted. In this case, the algorithm will simply pass through the array without shifting any elements.
• Worst Case: O(n²) – The worst case occurs when the array is sorted in reverse order. In this case, every element must be compared and shifted.
• Average Case: O(n²) – On average, Insertion Sort performs O(n²) comparisons and shifts.

💡 Space Complexity of Insertion Sort

• Space Complexity: O(1) – Insertion Sort is an in-place sorting algorithm, meaning it sorts the array without needing extra memory (except for a few temporary variables).

---

⚡ Why Use Insertion Sort?

While Insertion Sort is not the most efficient for large datasets, it has some benefits that make it useful in certain scenarios:

• Efficiency on Small or Nearly Sorted Arrays: It is particularly useful for small or nearly sorted arrays.
• Stability: Insertion Sort is stable, meaning it preserves the relative order of equal elements.
• Adaptive: It adapts well to arrays that are already partially sorted, reducing the number of comparisons and shifts needed.
• Simple Implementation: The algorithm is straightforward to implement and understand, making it useful for educational purposes.

However, for larger datasets, algorithms like Merge Sort or Quick Sort are preferred because they have better time complexity (O(n log n)).

---