Insertion Sort: Algorithm Implementation and Time Complexity

Introduction

Unsurprisingly, insertion sort does just what it sounds like--every subsequent element is inserted into its correct, sorted position within an array.

This comprehensive guide will cover all the bases of insertion sort, from its pros and cons and an implementation within C, to calculations of its time complexity.

Why Insertion Sort?

When dealing with sorting algorithms, programmers face compromise between time and memory--while some sorting methods are faster than others, they tend to use up more memory, and vice versa.

Insertion sort is something of the latter, taking up less memory, but also being a generally slower algorithm.

Advantages:

• Ideal for small and nearly-sorted lists

• In-place sorting algorithm

  • doesn’t require any additional memory, as all of the sorting occurs within the same array

  • basically, the program doesn’t create a new, temporary array for storage

• Stable sorting algorithm

  • relative order of elements is preserved once sorted

Disadvantages:

• Not so efficient for large lists

Insertion Sort in C

Before we jump into a full-fledged implementation of this sorting algorithm in C, it's always a good idea to have a general idea of what the program intends to do on a higher-level--that's where pseudocode comes in handy.

• Starting with the second element in the list, insertion sort looks at all the elements to the left of the "current element" and compares them

• If the element has not reached the beginning of the list AND if its value is less than the element to its left, the value checked is shifted one place to the right

• If the element has reached the very beginning of the list OR if its value is greater than the element to its left, the element is placed there

• This process continues until all elements in the list have been compared with the values to their left

Let's use the list [ 2, 5, 3, 9, 0 ] to simulate this. The number highlighted is the one being compared to the values to its left, and respectively inserted.

1. [ 2, 5, 3, 9, 0]
   

2. [ 2, 3, 5, 9, 0]

3. [ 2, 3, 5, 9, 0]

4. [ 0, 2, 3, 5, 9]

Now that we've established how this algorithm should work in theory, let's have a look at its formal implementation in C.

Note that the comments (denoted with //) can be helpful in understanding what each part of the program does!

#include <stdio.h>

// function prototype
void insertionSort(int arr[], int n);

int main()
{
    // initialize array, array length
    int array[] = {2, 5, 3, 9, 0};
    int length = sizeof(array) / sizeof(array[0]);
    
    // function call
    insertionSort(array, length);
}

void insertionSort(int arr[], int n)
{
    // insertion sort
	// begins at second element
    for (int i = 1; i < n; i++)
    {
        int j = i-1;
        int curNum = arr[i];
        
		// checks if elements to the left haven't reached the beginning or are greater than the current number being compared
        while (j >= 0 && curNum < arr[j])
        {
			// if so, shift the element to the right and change j one to the left
            arr[j+1] = arr[j];
            j--;
        }
        
		// once j has reached index -1 or the current number is greater than a value to its left, it gets inserted there
        arr[j+1] = curNum;
    }
    
    // prints array
    for (int i = 0; i < n; i++)
    {
        printf("%i", arr[i]);
    }
}

Calculating Time Complexity

Time Complexity is a measure of how efficient the program in terms of the amount of time it takes to run (and thus, the number of steps required to run the algorithm).

Of course, programs can vary in time complexity depending on how elements are placed in the original array, so we can account for the worst case and best case scenario using Big-O and Big-Omega notations (respectively), on which you can find more about in my CS50's Week 3 blog!

Best Case Scenario: all elements in the array are pre-sorted

In the case that all elements are sorted, only the outer for loop would run (as the conditions for the while loop would never be met). Thus, the program would run n -1 times, where n is the number of elements in the list.

Mathematically...

n - 1

Σ 1 = n-1

i = 1

Because n is the most prominent term, we can express this as Ω(n).

Worst Case Scenario: all elements in the array are in reverse order

Here, not only would the outer loop run n-1 times, but the inner loop would run i times, where i is the number of places from the current element to the beginning of the list.

Mathematically...

n - 1 i - 1  n - 1

Σ Σ 1 = Σ i = (1/2)(n-1)(n)

i = 1 j = 0 i = 1

Because the most prominent term is n^2, we can express this as Ο(n^2).

Final Thoughts

Ultimately, insertion sort can be an asset when working with specific datasets, so it can be especially useful to know the time and place for which using a sorting algorithm will help you (or harm you).

That's all for insertion sort!

Meanwhile, stay tuned for updates by following my blog and LinkedIn page.