Counting Sort is a kind of sort which you can use, only when you have prior knowledge about the kind of data you are sorting. For counting sort, we need to know about the range of the give data eg: o – 100, 200 – 1000. We do counting sort in two steps:
1. Count the number of times an element/ integer has occured in the given list.
2. perform prefix on the count array.
2. Find the position of the element according to count of elements which are before to it.
Following is the example demostrating counting sort:
Input: 5 1 5 1 3
count:2 0 1 0 2
prefix – count: 2 2 3 3 5
Output: 1 1 3 5 5
To find the output array, we do the following:
1. pick the element from the input array. Let us pick 5 which occured first and call it X.
2. Find the integer which is placed at X in the prefix count array. i.e. position = prefixCount[X-1].
3. This is the position of the element in the output and decrement the value of in the prefix-count array.
Following is the C code for counting sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
void countingSort(int , int *);
void display(int, int *);
/* Main Method takes the input from the users and performs counting sort on the input_array */
void main() {
int *input_array, size, index, ch;
srand(time(NULL));
printf("Enter the size of the array: ");
scanf("%d", &size);
input_array = (int *)malloc(sizeof(int) * size);
printf("\n\n1. Random Number Generation\n2. User Input\nEnter choice from above: ");
scanf("%d", &ch);
if(ch == 1){ //Random Generation
for(index=0; index<size; index++)
input_array[index] = rand()%99 + 1 ; //Will generate numbers in the range of 1 - 100.
} else if (ch == 2) { //User Input
printf("\nPlease enter value less than 100\n");
for(index = 0; index<size; index++) {
printf("\nEnter the element to be sorted: ");
scanf("%d", &input_array[index]);
while(1) {
if (input_array[index] < 0 || input_array[index] > 100) {
printf("Please enter only positive values and values less than 100 only:");
scanf("%d", &input_array[index]);
}
else
break;
}
}
}
else {
printf("\nPlease Enter correct Choice, re-run the program");
}
printf("\n\nRandomly Generated data is: ");
display(size, input_array);
countingSort(size, input_array);
}
void display(int size, int *array) {
int index;
for(index=0;index<size;index++)
printf("%d ", array[index]);
}
void countingSort(int size, int *input_array) {
int *count_array, *sorted_array, position, index;
count_array = (int *)calloc(100, sizeof(int));
sorted_array = (int *)malloc(sizeof(int) * size);
for (index=0;index<size;index++) //Find number of times item has appeared.
count_array[input_array[index]]++;
for (index=1;index<100;index++) //Perform prefix sum on count_array.
count_array[index] += count_array[index-1];
for (index=0;index<size;index++) { //Find the position fo the element and palce element inthat position of sorted_array.
position = count_array[input_array[index]]--;
sorted_array[position-1] = input_array[index];
}
printf("\n\nSorted array is: ");
display(size, sorted_array);
printf("\n");
}
The code performs counting sort.
Output:
Download code from here.
Letusprogram 