# Counting Sort in Data Structures

06 Jun 2024
Intermediate
2.45K Views
Learn via Video Course & by Doing Hands-on Labs

## 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

1. Find out the maximum element max from the given array.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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

1. Time Complexity
 Case Time Complexity Best O(n + k) Average O(n + k) Worst O(n + k)
2. 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

1. Counting sort is used when there are smaller integers with multiple counts.
2. When you need an algorithm with linear complexity.

## Advantages of Counting Sort Algorithm

1. 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.
2. Counting sort is easy to code.
3. Counting sort is a stable algorithm i.e. it maintains the relative order of elements with equal values.

## Disadvantages of Counting Sort Algorithm

1. Counting sort doesn’t work on decimal values. It is designed for sorting integer values.
2. Counting sort is inefficient if the range of values to be sorted is very large.
3. 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 Best Data Structures And Algorithms Course.

## FAQs

### Q1. Is counting sort stable?

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.

### Q2. Is counting sort an in-place sorting algorithm?

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.

### Q3. Where should counting sort be used?

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.
Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 ASP.NET Core Project Jul 16 TUE, THU Filling Fast 07:00AM to 08:30AM (IST) Azure Master Class Jul 20 SAT, SUN Filling Fast 03:00PM to 05:00PM (IST) ASP.NET Core Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Software Architecture and Design Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) .NET Solution Architect Certification Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) Azure Developer Certification Training Jul 28 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Data Structures and Algorithms Training with C# Jul 28 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Aug 11 SAT, SUN Filling Fast 09:30AM to 11:30AM (IST) ASP.NET Core Project Aug 24 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST)

Can't find convenient schedule? Let us know

Similar Articles