C Program to Implement Counting Sort

Introduction

Counting Sort is a non-comparative sorting algorithm that sorts a collection of elements by counting the occurrences of each unique element. The algorithm works efficiently on datasets where the range of input values is not significantly larger than the number of elements to be sorted. Counting Sort is particularly useful for sorting integers and characters when the range of values is known.

Example:

• Input: Unsorted array [4, 2, 2, 8, 3, 3, 1]
• Output: Sorted array [1, 2, 2, 3, 3, 4, 8]

Problem Statement

Create a C program that:

• Implements the Counting Sort algorithm to sort an array of non-negative integers.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Counting Sort Function: This function will count the occurrences of each element and then calculate the positions in the sorted array.
3. Create a Main Function: Allow the user to input the array, apply counting sort, and display the sorted array.

C Program to Implement Counting Sort

#include <stdio.h>
#include <stdlib.h>

// Function to find the maximum element in the array
int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// Function to implement Counting Sort
void countingSort(int arr[], int n) {
    // Find the maximum element to know the range of the count array
    int max = findMax(arr, n);

    // Create a count array to store the count of each unique element
    int *count = (int *)malloc((max + 1) * sizeof(int));

    // Initialize the count array with zeros
    for (int i = 0; i <= max; i++) {
        count[i] = 0;
    }

    // Store the count of each element
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Store the cumulative count of the elements
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // Create an output array to store the sorted elements
    int output[n];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy the sorted elements into the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    // Free the dynamically allocated memory for count array
    free(count);
}

int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Apply Counting Sort
    countingSort(arr, n);

    // Output the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Find the Maximum Element in the Array

• The findMax function scans the entire array to find the maximum value. This is essential for determining the size of the count array.

Function to Implement Counting Sort

• The countingSort function sorts the array by counting the occurrences of each element and then calculating the cumulative counts to determine the correct positions in the output array.
• The steps are as follows:
  1. Count Array Initialization: Create and initialize a count array based on the range of input values.
  2. Count Occurrences: Count the occurrences of each element in the input array.
  3. Cumulative Count: Calculate the cumulative count to determine the positions of elements in the sorted array.
  4. Build Output Array: Place the elements in their correct positions in the output array based on the cumulative counts.
  5. Copy to Original Array: Copy the sorted elements from the output array back to the original array.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Counting Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 7
Enter 7 elements:
4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

Example Output (Single Element Array):

Enter the number of elements in the array: 1
Enter 1 element:
5
Sorted array: 5

Conclusion

This C program demonstrates how to implement Counting Sort, an efficient sorting algorithm for arrays with a limited range of integer values. Counting Sort is particularly useful when the range of values is small relative to the number of elements in the array. The program provides a practical example of how Counting Sort can be implemented in C programming to achieve stable and efficient sorting.