Insertion Sort

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages, such as simplicity and efficiency for small data sets or nearly sorted lists.

Here’s how the Insertion Sort algorithm works:

1. Start from the second element: Begin with the second element of the array (or list). Assume the first element to be already sorted.
2. Insertion process: For each element, compare it with the elements to its left and move it to its correct position within the sorted part of the array.
3. Repeat: Continue this process for each element in the array until the entire array is sorted.

Here’s an implementation of the Insertion Sort algorithm 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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {11, 21, 43, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("\nSorted array: \n");
    printArray(arr, n);
    
    return 0;
}

Output:

Original array: 
11 21 43 5 6 

Sorted array: 
5 6 11 21 43 

Time Complexity

The time complexity of the Insertion Sort algorithm is O(n2) in the worst-case scenario and O(n) in the best-case scenario.

Here’s a breakdown of the time complexity:

1. Worst-case scenario: In the worst case, the array is in reverse sorted order. For each element in the array, the algorithm needs to compare it with all the elements to its left, resulting in approximately n(n−1)/2​ comparisons and swaps, where n is the number of elements in the array. Thus, the time complexity is O(n2).
2. Best-case scenario: In the best case, the array is already sorted. In this scenario, the algorithm only needs to iterate through the array once, resulting in n−1 comparisons and no swaps. Thus, the time complexity is O(n).