Insertion Sort

Insertion Sort

Description: Insertion sort is a simple and intuitive sorting algorithm that builds a sorted list one element at a time. It works by taking an element from the unsorted portion and inserting it into the correct position in the sorted portion of the list.

How It Works

1. Initialization: Start with the first element as the sorted portion of the array.
2. Take Element: Pick the next element from the unsorted portion.
3. Insert: Compare it with the elements in the sorted portion from right to left, shifting elements as necessary to make room for the new element.
4. Place Element: Insert the new element into its correct position.
5. Repeat: Continue this process until all elements have been sorted.

Time Complexity

• Worst Case: $O(n^2)$ — occurs when the array is sorted in reverse order.
• Average Case: $O(n^2)$
• Best Case: $O(n)$ — occurs when the array is already sorted.

Space Complexity

• Space Complexity: $O(1)$ — insertion sort is an in-place sorting algorithm, which means it requires only a constant amount of additional storage space.

Stability

• Stability: Insertion sort is a stable sort. Equal elements maintain their relative order after sorting.

Example Code

Here's a C++ implementation of insertion sort:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // Element to be inserted
        int j = i - 1;
        
        // Shift elements of arr[0..i-1] that are greater than key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // Place key at its correct position
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definition: The insertionSort function takes an array and its size as parameters.
2. Outer Loop: Iterates from the second element (index 1) to the last element.
3. Key Element: The current element is stored in key, which will be inserted into the sorted portion of the array.
4. Inner Loop: The inner while loop shifts elements in the sorted portion that are greater than key to the right, creating a space for key.
5. Insert Key: Once the correct position is found, key is inserted into the array.
6. Output: After sorting, the program prints the sorted array.

Conclusion

Insertion sort is efficient for small data sets or nearly sorted arrays. While it has a quadratic time complexity in the worst case, its best-case performance and stability make it useful in practice for certain scenarios. Insertion sort is often used in conjunction with other algorithms, like in hybrid sorting algorithms, where it efficiently sorts small subarrays.