C Counting Sort: A Practical Guide for Beginners 🎯

Welcome to your journey through C Programming! Today, we'll dive into one of the most effective sorting algorithms: Counting Sort. By the end of this lesson, you'll understand how it works, why it's useful, and even write your own implementation! 💡

Understanding Counting Sort 📝

Counting Sort is a simple yet efficient sorting algorithm that works best on arrays with distinct elements. It sorts an array by counting the occurrences of each element and then building an array to hold the sorted elements.

Breaking Down Counting Sort 📝

Initialize an array count[] to store the count of each element in the input array arr[].
Initialize another array cumulative[] to store the cumulative count of each element.
Build an array output[] to store the sorted elements.
Place the elements of the input array arr[] into the output[] array according to their count.
Return the sorted array output[].

Let's make it more concrete with an example! ✅

Practical Example 📝

Let's say we have an array arr[]:

int arr[] = {4, 2, 2, 8, 3, 3, 1};

Here's how we'd implement Counting Sort:

#include <stdio.h>

void countingSort(int arr[], int n) {
    int i, count[10] = {0}, output[n];

    // Step 1: Initialize the count array
    for (i = 0; i < 10; i++)
        count[i] = 0;
    for (i = 0; i < n; i++)
        count[arr[i]]++;

    // Step 2: Initialize the cumulative count array
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Step 3: Build the output array
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Step 4: Copy the sorted elements to the main array
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

// Driver code
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 5: Call the counting sort function
    countingSort(arr, n);

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

    return 0;
}

Running the above code will output 1 2 2 3 3 4 8, which is the sorted version of our input array! ✅

When to Use Counting Sort 📝

Counting Sort is particularly useful when the input array has distinct elements. It has a time complexity of O(n + k), where n is the size of the array and k is the range of the elements. The space complexity is O(n + k), which can be a bit high for large arrays.

Test Your Knowledge 🎯

Now that you've mastered Counting Sort, you're one step closer to becoming a C programming pro! Keep practicing, and remember to always ask questions if you're stuck. 💡 Happy coding! 🚀