C Exercises: Return the counting sort on an array

Last update on March 18 2025 13:21:14 (UTC/GMT +8 hours)

59. Counting Sort of an Array

Write a program in C to return the counting sort on an array.

Expected Output :
The given array is : 4 14 8 0 2 5 2 1 0 17 9 0 5
After sorting the elements in the array are: 0 0 0 1 2 2 4 5 5 8 9 14 17

To perform counting sort on an array, the program first determines the range of the input values. It then creates a count array to store the frequency of each element. By accumulating the counts and then using them to place elements in their correct positions, the program efficiently sorts the array. This algorithm is particularly effective for arrays with a limited range of integer values.

Sample Solution:

C Code:

#include <stdio.h>

// Function to perform counting sort on the array
void counting_sort(int arr1[], int n, int max) {
    int count[50] = {0}; // Initializing an array to store count of elements
    int i, j;

    // Counting occurrences of each element in the array
    for (i = 0; i < n; ++i)
        count[arr1[i]] = count[arr1[i]] + 1;

    printf("After sorting the elements in the array are:  ");

    // Reconstructing the sorted array using count array
    for (i = 0; i <= max; ++i) {
        for (j = 1; j <= count[i]; ++j) {
            printf("%d ", i); // Printing the element based on its count
        }
    }
}

int main() {
    int max = 0; // Initializing max value
    int arr1[] = {4, 14, 8, 0, 2, 5, 2, 1, 0, 17, 9, 0, 5};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int i;

    //------------- print original array ------------------
    printf("The given array is :  ");
    for (i = 0; i < n; i++) {
        if (arr1[i] > max)
            max = arr1[i]; // Finding maximum element in the array
        printf("%d  ", arr1[i]);
    }
    printf("\n");
    //------------------------------------------------------

    counting_sort(arr1, n, max); // Function call for counting sort
    return 0;
}

Output:

The given array is :  4  14  8  0  2  5  2  1  0  17  9  0  5  
After sorting the elements in the array are:  0 0 0 1 2 2 4 5 5 8 9 14 17

Flowchart:/p> Flowchart: Return the counting sort on an array.

For more Practice: Solve these Related Problems:

Write a C program to implement counting sort on an array and then verify the output by comparing with qsort().
Write a C program to perform counting sort on an array of non-negative integers and display the frequency of each element.
Write a C program to implement counting sort and then modify it to sort characters in a string.
Write a C program to apply counting sort on an array and then reverse the sorted array.

C Programming Code Editor:

Previous: Write a program in C to move all zeroes to the end of a given array.
Next: Write a program in C to find the row with maximum number of 1s.