Data Structures and Algorithms - Insertion Sort - Day 4

What is Insertion Sort

Insertion sort is a sorting algorithm in which we build a sorted portion of the array from left to right. We begin by considering the element at index 0 as already sorted. Next, we move to index 1 and compare it with the elements to its left, swapping as needed until the left side of the array remains in order. This process ensures that, after each step, all elements up to the current index are sorted.

We repeat this procedure for each index until we reach the last element, resulting in a fully sorted array.

Example

Let’s consider the following array -

5 4 3 9 7

The size of the array a.k.a n = 5

We take two variables i and j for the outer and inner loop respectively.

We start i from 1 and end to n-1 by incrementing by 1

We start j from i and end at 1 by decrementing by 1

As after each loop the array is sorted upto the current index.

Now a psudocode for the loops will be -

i initialized to 1 and incremented by 1 up to n-1:
    j initialized to i and decremented by 1 up to 1:
        if the elemnet at index j of the array is greater than the element at index j-1 of array:
            perform swap so that index j-1 has the index j element and vice versa
        else:
            break out of the loop cause the rest of the array is sorted. 

so now

i = 1

for j=1 we compare elements as index 1 and 0 - in this case 4 and 5

Now as 4 < 5 we perform a swap and now the array looks like -

4 5 3 9 7

Now j becomes 0 and does not satisfy the condition of the inner loop so the inner loop ends and now

i = 2
j = 2

we compare elements as index 2 and 1 - in this case 3 and 5

Now as 3 < 5 we will perform another swap and the array will look like -

4 3 5 9 7

j decrements by 1 and now j=1

we compare elements as index 1 and 0 - in this case 3 and 4

Now as 3 < 4 so there will be a swap and the array will look like -

3 4 5 9 7

j decrements by 1 and now j=0

We exit out of the inner loop and i is incremented by 1

i = 3
j = 3

we compare elements as index 3 and 2 - in this case 9 and 5

as they are already in order, and the rest of the array is sorted we can immidiately break out of the inner loop. Resulting array -

3 4 5 9 7

Now i is incremented by 1 -

i = 4
j = 4

we compare elements as index 4 and 3 - in this case 7 and 9

Now as 7 < 9 so there will be a swap and the array will look like -

3 4 5 7 9

Now j decrements and j = 3 so we compare the elements at index 3 and 2 in this case 7 and 5. Now as 7 > 5 there will be no swap and as the rest of the array is sorted we can break out of the inner loop.

i is incremented and i = 5

As i is now no longer less than n(5) we break out of the outer loop and our sorted array is -

3 4 5 7 9

You can compare this with the bubble sort example to get a clean idea of how the sorts work differently.

Code

#include<stdio.h>

int main() {
    int n;

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

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

    int i, j, temp;

    for (i = 1; i < n; i++) {
        for (j = i; j > 0; j--) {
            if (arr[j] < arr[j-1]) {
                // swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }

            //otherwise it means we have the rest sorted
            else{
                break;
            }
        }
        //use this loop to see intermediate steps
        for (int k = 0; k < n; k++)
            printf("%d ", arr[k]);
        printf("\n");
    }

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

    return 0;
}

Time and space complexity (noted on 12th August)

Time and space complexity are important parameters to understand the efficiency of an algorithm.

For insertion sort in worst case (reverse sorted array) in first loop we go through 1 comparison, in 2nd we go through 2 … by n-1 we go through n-1 comparisons. So total statements executed - 1 + 2 + 3... +(n-1) i.e (n-1) * n / 2 i.e n^2 /2 - n/2

Now in complexity we take the higher degree so the time complexity for worst and average case is O(n²)

But in best case, after 1 comparison we will know the rest of the array is sorted, so in all cases the inner loop will run only once resulting in 1 + 1+ 1 ... [n-1 times] i.e. n-1 total comparisons, resulting in a O(n) complexity for best case

So time complexity for -

Best case - O(n) Average case - O(n^2) Worst case (reverse order array) - O(n^2)

This is the main difference between bubble sort and insertion sort.

As we are not requiring any additional space it has a constant or O(1) complexity.