C Programming: Insertion Sort 🎯

Welcome to our comprehensive guide on C Programming's Insertion Sort! This lesson is designed for beginners and intermediates, so don't worry if you're just starting out. By the end of this tutorial, you'll have a solid understanding of Insertion Sort, its applications, and how to implement it in C. Let's dive in!

What is Insertion Sort? 📝

Insertion Sort is a simple sorting algorithm that works by repeatedly taking an element from the unsorted part of the list and inserting it into the correct position in the sorted part. It's particularly useful for small data sets and works well when the input data is almost sorted.

Why Use Insertion Sort? 💡

Easy to understand and implement
Stable sorting algorithm (preserves the original order of equal elements)
Efficient for small data sets and nearly sorted lists

Implementing Insertion Sort in C 📝

Here's a simple example of Insertion Sort in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Quiz: What is the output of the above code? 📝

In the next sections, we'll delve deeper into Insertion Sort, explore its efficiency, and practice with more examples. Stay tuned! 🎯