Start Learning Free
Previous Tutorial
02
MayCounting Sort in Data Structures
15 Jan 2025
Intermediate
5.61K Views
16 min read
Learn with an interactive course and practical hands-on labs
Free DSA Online Course with Certification
Counting Sort: An Overview
In this DSA tutorial, we will learn about the counting sort algorithm that works by counting each distinct element in the array. To further enhance your understanding and application of counting sort concepts, consider enrolling in the Dsa Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.
What is Counting Sort in Data Structures?
Counting sort is a linear non-comparison-based sorting algorithm that works great for a specific range of values. It counts the number of occurrences of each distinct element in an array and uses that information to determine the sorted order. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.
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
Working of the Counting Sort Algorithm
- Find out the maximum element max from the given array.
- Initialize an array of length max+1 with all elements 0. This array is used for storing the count of the elements in the array.
- Store the count of each element at their respective index in the count array
For example: if the count of element 3 is 2 then, 2 is stored in the 3rd position of the count array. If element 6 is not present in the array, then 0 is stored in 6th position.
- Store the cumulative sum of the elements of the count array. It helps in placing the elements into the correct index of the sorted array.
- Find the index of each element of the original array in the count array. This gives the cumulative count. Place the element at the index calculated as shown in the figure below.
- After placing each element in its correct position, decrease its count by one.
Read More - Data Structure Interview Questions for Experience
Implementation of Counting Sort in Different Languages in Data Structures
def countingSort(array):
size = len(array)
output = [0] * size
# Initialize count array
count = [0] * 10
# Store the count of each element in the count array
for i in range(0, size):
count[array[i]] += 1
# Store the cumulative count
for i in range(1, 10):
count[i] += count[i - 1]
# Find the index of each element of the original array in the count array
# Place the elements in the output array
i = size - 1
while i >= 0:
output[count[array[i]] - 1] = array[i]
count[array[i]] -= 1
i -= 1
# Copy the sorted elements into the original array
for i in range(0, size):
array[i] = output[i]
def print_list(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
arr = [5, 3, 3, 9, 4, 4, 1]
print("Original array is:", end=" ")
print_list(arr)
countingSort(arr)
print("Sorted Array in Ascending Order:", end=" ")
print_list(arr)
public class CountingSort {
static void countingSort(int[] array) {
int size = array.length;
int[] output = new int[size];
// Initialize count array
int[] count = new int[10];
// Store the count of each element in the count array
for (int i = 0; i < size; i++) {
count[array[i]] += 1;
}
// Store the cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Find the index of each element of the original array in the count array
// Place the elements in the output array
int i = size - 1;
while (i >= 0) {
output[count[array[i]] - 1] = array[i];
count[array[i]] -= 1;
i -= 1;
}
// Copy the sorted elements into the original array
System.arraycopy(output, 0, array, 0, size);
}
static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {5, 3, 3, 9, 4, 4, 1};
System.out.print("Original array is: ");
printArray(arr);
countingSort(arr);
System.out.print("Sorted Array in Ascending Order: ");
printArray(arr);
}
}
#include <iostream>
using namespace std;
void countingSort(int array[], int size) {
int output[size];
// Initialize count array
int count[10] = {0};
// Store the count of each element in the count array
for (int i = 0; i < size; i++) {
count[array[i]] += 1;
}
// Store the cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Find the index of each element of the original array in the count array
// Place the elements in the output array
int i = size - 1;
while (i >= 0) {
output[count[array[i]] - 1] = array[i];
count[array[i]] -= 1;
i -= 1;
}
// Copy the sorted elements into the original array
copy(output, output + size, array);
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {5, 3, 3, 9, 4, 4, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original array is: ";
printArray(arr, size);
countingSort(arr, size);
cout << "Sorted Array in Ascending Order: ";
printArray(arr, size);
return 0;
}
Output
Original array is: 5 3 3 9 4 4 1
Sorted Array in Ascending Order: 1 3 3 4 4 5 9
Complexity Analysis of Counting Sort Algorithm
- Time Complexity
Case Time Complexity Best O(n + k) Average O(n + k) Worst O(n + k) - Space Complexity: Here, we use an additional array of size K, which is the maximum element of the array to store the frequencies of all the elements in the range [0, K]. Thus, the space complexity largely depends on the value of K, and is equivalent to O(K).
Applications of Counting Sort Algorithm
- Counting sort is used when there are smaller integers with multiple counts.
- When you need an algorithm with linear complexity.
Advantages of Counting Sort Algorithm
- Counting sort generally performs faster than all comparison-based sorting algorithms, such as merge sort and quick sort, if the range of input is of the order of the number of inputs.
- Counting sort is easy to code.
- Counting sort is a stable algorithm i.e. it maintains the relative order of elements with equal values.
Disadvantages of Counting Sort Algorithm
- Counting sort doesn’t work on decimal values. It is designed for sorting integer values.
- Counting sort is inefficient if the range of values to be sorted is very large.
- Counting sort is not an in-place sorting algorithm. It uses extra space for sorting the array elements.
Summary
So, here we saw every aspect of the counting sort algorithm in data structures. The power of Counting Sort is its linear running time. It works differently compared to the sorting algorithms we have learned so far. To apply your knowledge of counting sort algorithm, enroll in our Free Data Structures And Algorithms Course.
Similar Sorting Algorithms
FAQs
Yes, counting sort is an example of a stable sorting algorithm, as it does not change the relative order of elements of the same value in the input.
No, counting sort is not an in-place sorting algorithm. In counting sort, we use an auxiliary array of the size of the range of data.
Counting sort works better than the other comparison-based sorting algorithms when we have to sort many numbers that lie in a comparatively smaller range on the number line.
Unlimited live sessions
Quick notes
Hands-on labs
Real-world projects
Interview prep