C Programming

Insertion Sort Time Complexity

Consider the following numbers:

50 60 30 10 80 70 20 40

If this list is sorted in ascending order, it would be:

10 20 30 40 50 60 70 80

If it is sorted in descending order, it would be:

80 70 60 50 40 30 20 10

Insertion sort is a sorting algorithm that is used to sort the list in ascending order or in descending order. This article deals only with sorting in ascending order. Sorting in descending order follows the same logic given in this document. The aim of this article is to explain the insertion sort. Programming is done in the following example in C. The insertion sort is explained here using one array.

Algorithm for Insertion Sort

An unsorted list is given. The aim is to sort the list in ascending order using the same list. Sorting an unsorted array using the same array is said to be sorting in-place. The zero based indexing is used here. The steps are as follows:

    • The list is scanned from the beginning.
    • While the scanning is going on, any number less than its predecessor is swapped with its predecessor.
    • This swapping continues along the list, until it is no longer possible to swap.
    • When scanning reaches the end, the sorting is complete.

Insertion Sort Illustration

When dealing with time complexity, it is the worst case that is normally taken into consideration. The worst arrangement for the previous list is:

80 70 60 50 40 30 20 10

There are eight elements with indexes from zero to 7.

At index zero, the scanning goes to 80. This is one movement. This one movement is an operation. There is a total of one operation so far (one movement, no comparison, and no swap). The result is:

| 80 70 60 50 40 30 20 10

At index one, there is a movement to 70. 70 is compared with 80. 70 and 80 are swapped. One movement is one operation. One comparison is also one operation. One swap is also one operation. This section provides three operations. There is a total of four operations so far (1 + 3 = 4). The result is as follows:

70 | 80 60 50 40 30 20 10

At index two, there is a movement to 60. 60 is compared with 80, then 60 and 80 are swapped. 60 is compared with 70, then 60 and 70 are swapped. One movement is one operation. Two comparisons are two operations. Two swaps are two operations. This section provides five operations. There is a total of nine operations so far (4 + 5 = 9). The result is as follows:

60 70 | 80 50 40 30 20 10

At index three, there is a movement to 50. 50 is compared with 80, then 50 and 80 are swapped. 50 is compared with 70, then 50 and 70 are swapped. 50 is compared with 60, then 50 and 60 are swapped. One movement is one operation. Three comparisons are three operations. Three swaps are three operations. This section provides seven operations. There is a total of sixteen operations so far (9 + 7 = 16). The result is as follows:

50 60 70 | 80 40 30 20 10

At index four, there is a movement to 40. 40 is compared with 80, then 40 and 80 are swapped. 40 is compared with 70, then 40 and 70 are swapped. 40 is compared with 60, then 40 and 60 are swapped. 40 is compared with 50, then 40 and 50 are swapped. One movement is one operation. Four comparisons are four operations. Four swaps are four operations. This section provides nine operations. There is a total of twenty-five operations so far (16 + 9 = 25). The result is as follows:

40 50 60 70 80 | 30 20 10

At index five, there is a movement to 30. 30 is compared with 80, then 30 and 80 are swapped. 30 is compared with 70, then 30 and 70 are swapped. 30 is compared with 60, then 30 and 60 are swapped. 30 is compared with 50, then 30 and 50 are swapped. 30 is compared with 40, then 30 and 40 are swapped. One movement is one operation. Five comparisons are five operations. Five swaps are five operations. This section provides eleven operations. There is a total of thirty-six operations so far (25 + 11 = 36). The result is as follows:

30 40 50 60 70 80 | 20 10

At index six, there is a movement to 20. 20 is compared with 80, then 20 and 80 are swapped. 20 is compared with 70, then 20 and 70 are swapped. 20 is compared with 60, then 20 and 60 are swapped. 20 is compared with 50, then 20 and 50 are swapped. 20 is compared with 40, then 20 and 40 are swapped. 20 is compared with 30, then 20 and 30 are swapped. One movement is one operation. Six comparisons are six operations. Six swaps are six operations. This section provides thirteen operations. There is a total of forty-nine operations so far (36 + 13 = 49). The result is as follows:

20 30 40 50 60 70 80 | 10

At index seven, there is a movement to 10. 10 is compared with 80, then 10 and 80 are swapped. 10 is compared with 70, then 10 and 70 are swapped. 10 is compared with 60, then 10 and 60 are swapped. 10 is compared with 50, then 10 and 50 are swapped. 10 is compared with 30, then 10 and 40 are swapped. 10 is compared with 30, then 10 and 30 are swapped. 10 is compared with 20, then 10 and 20 are swapped. One movement is one operation. Seven comparisons are seven operations. Seven swaps are seven operations. This section provides fifteen operations. There is a total of sixty-four operations so far (49 + 15 = 64). The result is as follows:

10 20 30 40 50 60 70 80 10 |

The job is done! 64 operations were involved.

64 = 8 x 8 = 82

Time Complexity for Insertion Sort

If there are n elements to sort with Insertion Sort, the maximum number of possible operations would be n2, as demonstrated previously. The Insertion Sort Time complexity is:

O(n2)

This uses the Big-O notation. The Big-O notation begins with O in uppercase, followed by parentheses. Inside the parentheses is the expression for the maximum possible number of operations.

Coding in C

At the very beginning of the scan, the first element cannot change its position. The program is essentially the following:

    #include <stdio.h>

    void insertionSort(int A[], int N) {
        for (int i=0; i<N; i++) {
            int j = i;
            while (A[j] < A[j-1] && j-1 >= 0) {
                int temp = A[j]; A[j] = A[j-1]; A[j-1] = temp;  //swap
                j--;
            }
        }
    }

 
The insertionSort() function definition uses the algorithm as described. Note the conditions for the while-loop. A suitable C main function for this program is:

    int main(int argc, char **argv)
    {
        int n = 8;
        int A[] = {50,  60, 30,  10,  80,  70,  20,  40};

        insertionSort(A, n);

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

        return 0;
    }

 

Conclusion

The time complexity for Insertion Sort is given as:

O(n2)

The reader might have heard of a worse-case time complexity, average-case time complexity and best-case time complexity. These variations of the Insertion Sort Time Complexity are discussed in the next article in our website.

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.