Counting Sort in C – Algorithm and Program
Counting Sort
Counting sort is effective sorting algorithm when range is not greater than number of objects to be sorted. This sort can be used to sorting the negative input values.This sorting algorithm that sorts the data of an array by count the number of occurrences of each unique element in the array.
Working of counting sort algorithm
Suppose the elements of array are –
1.Firstly, Find the maximum element from the given array. Suppose max be the maximum element.
2.Initialize array of length max + 1 having all zero elements. And this array used to store the count of the elements in the given array.
3. Now, we store the count of each array element at their corresponding index in array.
The count of an element stored as – Let array element ‘4’ is appeared two times, so the count of element 4 is 2. Hence, 2 is stored at the 4th position of the count array. If any element is absent in the array, place 0, i.e. suppose element ‘3’ is absent in the array, so, 0 will be stored at 3rd position.
Now, store cumulative sum of count array elements and it is used to place the elements at the correct index of the sorted array.
The cumulative count of the count array is given below-
4. After that, find the index of each element of the original array
After placing element at their place, decrease its count by 1. Before placing element 2, its count was 2, but after placing it at right position, then new count for element 2 is 1.
Similarly, after sorting, the array elements are given as below
Now, the array is completely sorted.
Counting Sort Algorithm
countingSort(array, size) max <- find largest element in array initialize count array with all zeros for j <- 0 to size find the total count of each unique element and store the count at jth index in count array for i <- 1 to max find the cumulative sum and store it in count array itself for j <- size down to 1 restore the elements to array decrease count of each element restored by 1
Program of counting sort in C
#include <stdio.h> void countingSort(int array[], int size) { int output[10]; int max = array[0]; for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } int count[10]; for (int i = 0; i <= max; ++i) { count[i] = 0; } for (int i = 0; i < size; i++) { count[array[i]]++; } for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } // Copy the sorted elements for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Function void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } int main() { int array[] = {4, 2, 2, 8, 3, 3, 1}; int n = sizeof(array) / sizeof(array[0]); countingSort(array, n); printArray(array, n); }
Output
1 2 2 3 3 4 8
Program of counting sort in C++
#include <iostream> using namespace std; void countSort(int array[], int size) { int output[10]; int count[10]; int max = array[0]; // largest element of the array for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } // Initialize count array for (int i = 0; i <= max; ++i) { count[i] = 0; } for (int i = 0; i < size; i++) { count[array[i]]++; } for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } // Copy the sorted elements for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Function void printArray(int array[], int size) { for (int i = 0; i < size; i++) cout << array[i] << " "; cout << endl; } // Driver code int main() { int array[] = {4, 2, 2, 8, 3, 3, 1}; int n = sizeof(array) / sizeof(array[0]); countSort(array, n); printArray(array, n); }
Output
1 2 2 3 3 4 8
Use of Counting Sort
- There are smaller integers with multiple counts.
- Needed the linear complexity.
Read more, Merge sort