Insertion Sort

Example:

We have an unsorted array:
[64, 25, 12, 22, 11]

The goal is to sort this array in ascending order using Insertion Sort, which works by iteratively building a sorted portion of the array.

---

Step-by-Step Execution:

Initial Array: [64, 25, 12, 22, 11]

1. Pass 1:

   • The first element, 64, is already considered sorted.

   • The second element, 25, is compared with 64. Since 25 < 64, we shift 64 to the right and insert 25 at the beginning.
     Array after Pass 1: [25, 64, 12, 22, 11]

2. Pass 2:

   • The third element, 12, is compared with 64 and then 25.

   • Since 12 < 64 and 12 < 25, we shift both 64 and 25 to the right and insert 12 at the beginning.
     Array after Pass 2: [12, 25, 64, 22, 11]

3. Pass 3:

   • The fourth element, 22, is compared with 64, then 25.

   • Since 22 < 64 but 22 > 25, we shift 64 to the right and insert 22 after 25.
     Array after Pass 3: [12, 22, 25, 64, 11]

4. Pass 4:

   • The fifth element, 11, is compared with 64, 25, 22, and 12.

   • We shift all elements to the right and insert 11 at the beginning.
     Array after Pass 4: [11, 12, 22, 25, 64]

Final Sorted Array: [11, 12, 22, 25, 64]

---

Pseudocode for Insertion Sort

InsertionSort(arr, n)
1. Start
2. Input the array `arr` of size `n`.
3. For `i = 1 to n-1`:                     # Outer loop (from second element to last)
    a. Set `key = arr[i]`                   # Key is the current element to be inserted
    b. Set `j = i - 1`                      # Set `j` to the index before `i`
    c. While `j >= 0` and `arr[j] > key`:   # Shift elements of arr[0..i-1] that are greater than `key`
        i. Set `arr[j+1] = arr[j]`           # Shift element to the right
        ii. Decrement `j` by 1
    d. Set `arr[j+1] = key`                  # Insert the key at its correct position
4. Output the sorted array `arr`.
5. End

---

Algorithm for Insertion Sort

1. Input: An array arr of size n.

2. Outer Loop: Begin at the second element (index 1) and iterate to the last element.

3. For each element arr[i] (the "key"):

   • Compare the key with the elements before it (from arr[i-1] to arr[0]).

   • Shift all larger elements to the right to make space for the key.

   • Insert the key in its correct position.

4. Once all elements are processed, the array will be sorted.

5. Output: Sorted array.

---

C Code: Function to Perform Insertion Sort

#include <stdio.h>

// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
    int i, key, j;

    // Outer loop to go through each element starting from the second
    for (i = 1; i < n; i++) {
        key = arr[i];    // The current element to be inserted
        j = i - 1;       // The index before the current element

        // Shift elements of arr[0..i-1] that are greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        // Insert the key at the correct position
        arr[j + 1] = key;
    }
}

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

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

    printf("Original Array: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted Array: ");
    printArray(arr, n);

    return 0;
}

---

Explanation of the Code

1. Outer Loop (i):
   Starts from the second element (index 1) and moves to the last element. This element is the "key" that needs to be inserted into the sorted portion of the array.

2. Key Element:
   The key is the element that needs to be placed in its correct position within the sorted part of the array.

3. Inner While Loop:
   Compares the key with elements before it (arr[j]), and if an element is greater than the key, it is shifted one position to the right.

4. Insertion:
   Once the correct position is found for the key, it is placed in that position (arr[j+1]).

---

Complexity Analysis of Insertion Sort