Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) 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, it has the advantage of being simple to understand and implement.

Here's a step-by-step explanation of how insertion sort works, using a small array of 5 elements as an example:

Let's assume our array is: [5, 3, 4, 1, 2]

Initial State:

5 3 4 1 2
↑

(The arrow points to the current element being sorted)

Iteration 1:

• No action is needed on the first element (5), as it is the only element in the sorted section.

Iteration 2 (Sorting 3):

5 3 4 1 2
  ↑

• Compare 3 with 5. Since 3 is smaller, swap them.

After Iteration 2:

3 5 4 1 2
  ↑

Iteration 3 (Sorting 4):

3 5 4 1 2
    ↑

• Compare 4 with 5, since 4 is smaller, swap them.

• Then compare 4 with 3, no swap needed as 3 is smaller.

After Iteration 3:

3 4 5 1 2
    ↑

Iteration 4 (Sorting 1):

3 4 5 1 2
      ↑

• Compare 1 with 5, 1 is smaller, swap them.

• Compare 1 with 4, 1 is smaller, swap them.

• Compare 1 with 3, 1 is smaller, swap them.

After Iteration 4:

1 3 4 5 2
      ↑

Iteration 5 (Sorting 2):

1 3 4 5 2
        ↑

• Compare 2 with 5, 2 is smaller, swap them.

• Compare 2 with 4, 2 is smaller, swap them.

• Compare 2 with 3, 2 is smaller, swap them.

After Iteration 5:

1 2 3 4 5
        ↑

Final Sorted Array:

1 2 3 4 5

The array is now sorted.

Here's the pseudocode for the insertion sort algorithm:

function insertionSort(array)
    for i from 1 to length(array)
        // The current element to be sorted
        key = array[i]

        // Initialize j to the position before the current element
        j = i - 1

        // Move elements of array[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while j >= 0 and array[j] > key
            array[j + 1] = array[j]
            j = j - 1

        // Place the key at its correct position
        array[j + 1] = key

    return array

Here's a brief explanation of each step:

1. Start with the second element: The algorithm starts iterating from the second element of the array, as the first element is considered sorted by itself.

2. Key Element: This is the element which is currently being sorted. In each iteration, the algorithm tries to insert the key element into its correct position in the sorted part of the array.

3. Shifting Elements: If the key element is smaller than the elements in the sorted part of the array, those elements are shifted one position to the right to make space for the key element.

4. Insert the Key: Once the correct position is found (where all elements to the left are smaller), the key is placed in its rightful position.

5. Repeat Until Sorted: This process is repeated for each element until the entire array is sorted.

Here's the C code for the insertion sort algorithm, followed by a detailed explanation:

#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[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

Explanation of the Code:

1. Header File Inclusion:

    #include <stdio.h>
   

   This includes the Standard Input Output library for using the printf function.

2. Insertion Sort Function:

    void insertionSort(int arr[], int n) {
        ...
    }
   

   This function takes an array arr[] and its size n as arguments.

3. Looping Through the Array:

    for (i = 1; i < n; i++) {
        ...
    }
   

   The loop starts from the second element (index 1) since the first element is considered sorted by default.

4. Key Element:

    key = arr[i];
   

   The key variable holds the value of the current element being sorted.

5. Finding the Correct Position for Key:

    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
   

   This while loop moves each element that is greater than key one position to the right to make space for inserting the key.

6. Inserting the Key:

    arr[j + 1] = key;
   

   Once the correct position is found, the key is placed in its rightful position.

7. Print Function:

    void printArray(int arr[], int n) {
        ...
    }
   

   This function prints the elements of the array. It's used to display the array before and after sorting.

8. Main Function: The main function demonstrates the usage of insertionSort. It defines an array, calls insertionSort on it, and then prints the sorted array.

This C program efficiently implements the insertion sort algorithm, showcasing its utility in sorting small arrays. The key concept is the repositioning of elements to insert each element into its correct position, making the left part of the array sorted at each step.

Complexity analysis of the insertion sort algorithm involves evaluating its time complexity and space complexity. Let's break down both of these aspects:

Time Complexity

1. Best Case (Array is already sorted):

   • O(n)

   • In the best-case scenario, where the array is already sorted, the inner loop (the while loop) does not perform any swaps. The algorithm only needs to iterate through the array once, making the time complexity linear.

2. Average Case and Worst Case (Array is partially sorted or not sorted):

   • O(n^2)

   • In the average and worst cases, the inner loop can perform a significant amount of comparisons and swaps. In the worst case, where the array is sorted in reverse order, the inner loop does the maximum amount of work. For each element, it may need to compare and shift almost every other element, leading to a quadratic time complexity.

Space Complexity

• O(1)

• Insertion sort is an in-place sorting algorithm. It doesn't require any additional space that grows with the input size. The space used by the variables i, j, and key is constant, regardless of the size of the input array.

Important to note

• Best Case Time Complexity: O(n)

• Average Case Time Complexity: O(n^2)

• Worst Case Time Complexity: O(n^2)

• Space Complexity: O(1)

Insertion sort is efficient for small datasets or nearly sorted datasets because its overhead is low. However, its efficiency decreases significantly for large, unsorted datasets due to its quadratic time complexity.