Program 9 : Insertion Sort

Sort a given set of elements using Insertion sort and determine the time required to sort n elements. Repeat the experiment for different values of n and plot a graph of the time taken versus n.

Insertion Sort

Starts from a point, holding it as key for comparision, Compare with element behind, if larger, replace it in keys place (creates duplicate but the key value in held in key variable)

Step back and compare with value with key, if larger, move it one step forward, (erases previous duplicate and creates new duplicate)

There cannot be any value smaller behind this, so if any then the rest after it will be smaller only so stop the iteration and place the key value in the last value removed. (clears the duplicate)

or it can move back till 0, replacing key in 1 index.

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j, key;

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

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

int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    insertionSort(arr, n);
    displayArray(arr, n);

    return 0;
}

Insertion Sort: Algorithm

Insertion sort builds the final sorted array one item at a time by repeatedly:

1. Picking the next element (called the key).

2. Comparing it with elements in the sorted portion.

3. Shifting all elements larger than the key one position to the right.

4. Inserting the key in its correct sorted position.

Example:

Input: {5, 2, 4, 6, 1, 3}

• Pass 1: Insert 2 → {2, 5, 4, 6, 1, 3}

• Pass 2: Insert 4 → {2, 4, 5, 6, 1, 3}

• Pass 3: Insert 6 → {2, 4, 5, 6, 1, 3}

• Pass 4: Insert 1 → {1, 2, 4, 5, 6, 3}

• Pass 5: Insert 3 → {1, 2, 3, 4, 5, 6}

---

Time Complexity

Case	Comparisons	Time Complexity
Best	Already sorted	O(n)
Average	Random order	O(n²)
Worst	Reversed order	O(n²)

• Stable and In-place