Counting Sort Algorithm in C

Counting Sort Algorithm

Below is the step-by-step algorithm for Counting Sort:

1. Find the maximum value max in the given array.
    
2. Create a count array of size max+1 and initialize all values to 0.
    
3. Iterate through the input array and update the count array with the frequency of each element.
    
4. Modify the count array to store cumulative sums.
    
5. Construct the output array using the count array.
    
6. Copy the sorted elements back to the original array.

C Program for Counting Sort

#include <stdio.h>
void countingSort(int arr[], int n) {
    int i, max = arr[0];
    
    // Find the maximum value in the array
    for (i = 1; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    
    // Create count array and initialize it to zero
    int count[max + 1];
    for (i = 0; i <= max; i++) {
        count[i] = 0;
    }
    
    // Store the frequency of each element
    for (i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // Modify count array to store cumulative sum
    for (i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }
    
    // Output array to store sorted elements
    int output[n];
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    
    // Copy sorted elements back to original array
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

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

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    countingSort(arr, n);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output:

Original array: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

Complexity Analysis of Counting Sort

• Time Complexity:
  • Best Case: O(n + k)
     
  • Average Case: O(n + k)
     
  • Worst Case: O(n + k)
     
  • where n is the number of elements and k is the range of input values.
     
• Space Complexity: O(k + n) (for count array and output array)

Counting Sort performs well for small ranges of numbers but may not be efficient for very large values due to increased space complexity.

Advantages of Counting Sort

1. Fast for Small Ranges: Performs in linear time when k is small.
    
2. Stable Sorting Algorithm: Maintains relative order of equal elements.
    
3. Efficient for Fixed-Range Data: Suitable for sorting limited-range numbers, such as exam scores or ages.

Disadvantages of Counting Sort

1. Not Suitable for Large Numbers: Requires extra space for the count array.
    
2. Limited to Integer Sorting: Cannot sort floating-point numbers or complex data structures.
    
3. Inefficient for Large Range Inputs: If k is much larger than n, space usage becomes excessive.

Applications of Counting Sort

1. Sorting Test Scores: Used in educational software to rank students based on marks.
    
2. Character Sorting in Strings: Useful in lexicographic order sorting.
    
3. Distribution Counting: Applied in statistical analysis where frequency distributions are needed.

Frequently Asked Questions

Can Counting Sort be used for sorting negative numbers? 

No, Counting Sort does not handle negative numbers directly. You need to adjust the range by shifting values to positive.

Why is Counting Sort not comparison-based? 

Counting Sort sorts elements based on counting occurrences rather than comparing them, making it different from comparison-based sorting algorithms like QuickSort and MergeSort.

When should Counting Sort be avoided? 

Counting Sort should be avoided when dealing with large integers, floating-point numbers, or objects that require comparison-based sorting.

Conclusion

In this article, we discussed the Counting Sort Algorithm in C, a non-comparative sorting technique that works efficiently for sorting integers within a known range. It counts the occurrences of each element and uses this information to place them in the correct order. Counting Sort is useful for cases where the maximum value is not significantly larger than the number of elements. Understanding this algorithm helps in solving sorting problems efficiently.