Updated April 17, 2023
Introduction to Counting Sort in C
Counting sort in C is a sorting technique which is actually based on the input value range. As sorting is used to sort elements in a linear way, users need to maintain an auxiliary array which increases space requirement for sort algorithm implementation. But somehow, this is not a very space-efficient algorithm. The sorting algorithm sorts the elements of an array by taking each unique element’s occurrences in the array. In Computer Science, other than sorting the collection of elements in an array, it is also way much helpful or used as a subroutine in radix sort or any other sorting algorithm that can handle large keys much more efficiently.
Syntax:
There is no particular syntax for counting sort, as C is a type of language where we will be using some conditions and loops to perform counting sort.
- Basically, counting sort works exactly like a hashtag; users calculate the max value of the array to be sorted.
- Then the occurrences of each element in the array from 0 to length 1 and these are assigned to an auxiliary array. And this is used to retrieve a sorted version of the array.
- This algorithm has linear time complexity, but it also has space complexity which is way to high and only is used in cases where the array element range is closer to the size of the array.
Algorithm/Pseudo Code of Counting Sort in C
- First, we need to iterate the input array and find a maximum value present in the array.
- Then declare a new array with size max_value + 1 with 0 values.
- Count each of the elements in the array and increment these values by the corresponding index.
- Find the cumulative sum of the auxiliary array by adding current and previous frequency.
- And now, this cumulative array value signifies the location of an element in the sorted array.
- We need to iterate the auxiliary array from 0 to maximum.
- Having 0 at the corresponding index and reducing the count by 1 signifies the element’s second position if it exists in the input array.
- Now this actual received array to the input array.
Basically, the algorithm is based on three types of array:
- Input Array: To store input data.
- Output Array: Stores the sorted data values.
- Temporary Array: Data storage temporarily.
Examples of Counting Sort in C
Different examples are mentioned below:
Example #1
Simple Counting sort in C.
Code:
#include <stdio.h>
#include <string.h>
void countsorting(int arr[], int n, int n1)
{
// creating an integer array of size n for sorted array
int outputArray[n];
// creating an integer array of size n1, initialized by zero
int freqArray[n1];
memset(freqArray, 0, sizeof(freqArray));
// Using the value of each item in an input array as index,
for (int i = 0; i < n; i++) {
freqArray[arr[i]]++;
}
// Calculating starting index for each integer
int totalCount = 0;
for (int i = 0; i < n1; i++)
{
int oldEleCount = freqArray[i];
freqArray[i] = totalCount;
totalCount += oldEleCount;
}
// Copying to output array, and preserving order of inputs with equal keys
for (int i = 0; i < n; i++)
{
outputArray[freqArray[arr[i]]] = arr[i];
freqArray[arr[i]]++;
}
// copying output array back to the input array
for (int i = 0; i < n; i++) {
arr[i] = outputArray[i];
}
}
int main()
{
int arr[] = { 4, 5, 2, 2, 1, 5, 4, 5, 6, 10, 10, 9, 10, 3, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int n1 = 11;
countsorting(arr, n, n1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}Output:
So here in the above algorithm, you can check that we have followed some kind of logic above to get the required output.
Example #2
Counting sort in C.
Code:
#include <stdio.h>
void countingSort(int Array[], int n1, int n)
{
int i, j;
int X[15], Y[100];
for (i = 0; i <= n1; i++)
Y[i] = 0;
for (j = 1; j <= n; j++)
Y[Array[j]] = Y[Array[j]] + 1;
for (i = 1; i <= n1; i++)
Y[i] = Y[i] + Y[i-1];
for (j = n; j >= 1; j--)
{
X[Y[Array[j]]] = Array[j];
Y[Array[j]] = Y[Array[j]] - 1;
}
printf("The Sorted array : ");
for (i = 1; i <= n; i++)
printf("%d ", X[i]);
}
int main()
{
int n, n1 = 0, Array[15], i;
printf("Enter the Array count : ");
scanf("%d", &n);
printf("\nEnter the elements which needs sorting :\n");
for (i = 1; i <= n; i++)
{
scanf("%d", &Array[i]);
if (Array[i] > n1) {
n1 = Array[i];
}
}
countingSort(Array, n1, n);
printf("\n");
return 0;
}Output:
So this is one type of logic written to perform counting sort in an array.
Conclusion
Here we saw algorithmic steps which we have seen above, and as per the steps, we have solved few examples, which will give us a clear idea on how counting sort works and you people can try hands-on with the counting sort theory.
Recommended Articles
This is a guide to Counting Sort in C. Here we discuss the introduction, algorithm/pseudo code of counting sort in C and examples, respectively. You may also have a look at the following articles to learn more –
