Insertion Sort

Why did the insertion sort algorithm get invited to all the parties? Because it knew how to slide into the right place without causing a scene!

What is Insertion Sort?

Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted portion of the list one element at a time. It works by repeatedly taking the next unsorted element and inserting it into its correct position within the sorted portion of the list. Insertion Sort is named because it inserts elements into their proper place.

How it Works

Here's a step-by-step explanation of how Insertion Sort works:

1. Start with the first element as the sorted region (since a single element is always sorted).

2. For each unsorted element, compare it to elements in the sorted region from right to left until you find the correct position.

3. Insert the element into its correct position within the sorted region, shifting other elements to the right if necessary.

4. Expand the sorted region to include the newly added element.

5. Repeat steps 2-4 for each unsorted element until the entire list becomes sorted.

Insertion Sort is particularly efficient when dealing with small datasets or partially sorted data, as the number of comparisons and swaps is minimal when elements are already in the correct order.

Insertion Sort Code in Java:

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1] that are greater than key
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

Insertion Sort Code in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time and Space Complexity Analysis

The time complexity of Insertion Sort can be expressed mathematically as follows:

Let n be the number of elements in the array to be sorted.

• In the best-case scenario, when the input array is already sorted, Insertion Sort makes only n - 1 comparisons (each element compared once) and no swaps.

• In the worst-case scenario, when the input array is sorted in reverse order, Insertion Sort makes the maximum number of comparisons and swaps. In this case, for each element, it compares it to all the previous elements in the sorted region.

The total number of comparisons and swaps in the worst-case scenario can be calculated as the sum of the first (n-1) natural numbers, which is given by the formula:

$(1 + 2 + 3 + ... + (n-1) = \frac{n \cdot (n-1)}{2})$

So, in the worst-case scenario, the number of comparisons and swaps made by Insertion Sort is approximately $(\frac{n \cdot (n-1)}{2})$

Therefore, the worst-case time complexity of Insertion Sort can be mathematically expressed as:

$(T(n) = \frac{n \cdot (n-1)}{2} \approx \frac{n^2}{2})$

Asymptotically, the worst-case time complexity of Insertion Sort is O(n^2), which indicates that its performance degrades quadratically with the size of the input array. In the best-case scenario, when the input array is nearly sorted, the time complexity can be as low as O(n).

• So the time complexity is:

  • Worst-case: O(n^2)

  • Average-case: O(n^2)

  • Best-case: O(n) when the list is nearly sorted

• And the space complexity: O(1) (in-place sorting, no additional memory required)

Insertion Sort is efficient for small datasets or when dealing with partially sorted data. It performs well when the list is nearly sorted (best-case scenario). However, its worst-case time complexity of O(n^2) makes it inefficient for sorting large datasets compared to more efficient sorting algorithms like Quick Sort or Merge Sort.