Insertion Sort Implementation

Hello! In our last two lessons, we explored sorting algorithms that have a time complexity of O(n²), namely Bubble Sort and Selection Sort. You learned how they use different strategies—repeatedly swapping adjacent elements versus finding the minimum—to sort an array.

Today, we will dive into our third fundamental sorting algorithm: Insertion Sort. The goal of this lesson is to understand its logic and implement it in C. You'll see that Insertion Sort works by building up a sorted portion of the array one element at a time, much like how you might arrange a hand of playing cards. This intuitive approach has some interesting performance characteristics that we will begin to touch on.

1. The Insertion Sort Concept

Like Selection Sort, Insertion Sort conceptually divides the array into two parts: a sorted subarray and an unsorted subarray. However, its method is quite different.

The algorithm iterates through the array, starting with the second element. In each iteration, it takes one element from the unsorted part and "inserts" it into its correct position within the already sorted part. The sorted part grows by one element in each pass.

The most common analogy is sorting a hand of playing cards. Imagine you pick up cards one by one. Each new card you pick up, you insert into its correct position in the hand you are already holding, which is always kept sorted.

Let's watch a video that explains this card analogy and the general logic of Insertion Sort.

As you saw, the key operations are:

1. Select the next unsorted element.
2. Shift all elements in the sorted part that are greater than the selected element one position to the right.
3. Insert the selected element into the newly created "hole".

2. The Algorithm and Pseudocode

Now that you have a visual understanding, let's formalize the logic. The algorithm uses a nested structure:

• An outer loop iterates from the second element (i = 1) to the end of the array. The element at array[i] is the one we want to insert into the sorted portion.
• An inner loop (often a while loop) moves backward from position i-1. It compares the element to be inserted (let's call it key) with the elements in the sorted portion. If an element is greater than key, it's shifted one position to the right. This continues until we find an element smaller than or equal to key, or we reach the beginning of the array.
• Finally, key is placed in the correct position.

The same video you just watched provides a clear walkthrough of the pseudocode that captures this logic.

3. Implementing Insertion Sort in C

With the logic and pseudocode clear, we can now implement Insertion Sort in C. The C code will closely follow the structure we just reviewed.

We will use another video for a guided implementation walkthrough. This one is specifically focused on C programming.

The key piece of C code that implements the "shift and insert" logic is the while loop nested inside the for loop:

// 'i' is the index of the element being inserted
// 'key' holds the value of that element
int key = array[i]; 
int j = i - 1;

// Move elements of array[0..i-1], that are
// greater than key, to one position ahead
// of their current position
while (j >= 0 && array[j] > key) {
    array[j + 1] = array[j];
    j = j - 1;
}
array[j + 1] = key; // Insert the key into the 'hole'

4. Practice and Review

It's time to get hands-on with the code. The following resource provides a complete, clean C program for Insertion Sort.

Here is the complete program from the resource for you to work with:

#include <stdio.h>

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

void insertionSort(int array[], int size) {
    for (int step = 1; step < size; step++) {
        int key = array[step];
        int j = step - 1;

        // Compare key with each element on the left of it until an element 
        // smaller than it is found.
        // For descending order, change key < array[j] to key > array[j].
        while (j >= 0 && key < array[j]) {
            array[j + 1] = array[j];
            --j;
        }
        
        // Place key after the element just smaller than it.
        array[j + 1] = key;
    }
}

// Driver code
int main() {
    int data[] = {9, 5, 1, 4, 3};
    int size = sizeof(data) / sizeof(data[0]);
    
    printf("Unsorted array:\n");
    printArray(data, size);

    insertionSort(data, size);

    printf("Sorted array in ascending order:\n");
    printArray(data, size);
}

Your Task:

1. Compile and run this code to verify that it correctly sorts the data array.
2. Modify the insertionSort function to sort the array in descending order (from largest to smallest). The comment in the code gives you a direct hint on how to do this. This simple change will test your understanding of the comparison at the heart of the algorithm.

Conclusion

In this lesson, you have successfully learned about and implemented Insertion Sort. We've seen how its strategy of building a sorted subarray by inserting elements one by one provides an intuitive way to sort data.

Key Takeaways:

• Insertion Sort works by dividing the array into a sorted and an unsorted part.
• It iterates through the unsorted part, picking one element at a time and inserting it into its correct position in the sorted part.
• The core of the implementation involves an outer loop to select an element (key) and an inner while loop to shift larger elements to the right to make space for the key.

Preview of the Next Lesson:
We've now implemented three O(n²) sorting algorithms. But is Insertion Sort always O(n²)? What happens if you run it on an array that is already sorted? In the next lesson, we will analyze the time complexity of Insertion Sort, where you'll discover its unique advantage: a best-case time complexity of O(n). This makes it surprisingly effective for nearly-sorted datasets.