Back to home

- What Is Counting Sort Algorithm?
- Algorithm of Counting
- Implementation
- Time & Space Complexity Analysis

Logicmojo - Updated Sept 18, 2021

Sorting is a near ubiquitous process in our daily lives. It makes sense to organize things to better use them. The same can be said for data. In computer programmingโand mathematics, for that matterโsorting algorithms are frequently used to order data as needed to perform a calculation, feed an engine, render an interface, etc.

There are several well known sorting algorithms: e.g. bubble, quick, selection, insertion, merge, heap, bucket. There is also a lesser known sorting algorithm, relegated to the proverbial annex like poor Toby: counting sort. Have you ever heard of it? It is infrequently used because it comes with some caveats which make it impractical in most use cases.

Counting sort is a sorting algorithm that sorts the elements with the technique of counting the number of occurrences of each unique element in an array or list. Counting algorithm is basically a hashing technique with the keys between a specific range and then counting the number of objects having distinct key values. Lastly, we will get the output sequence by doing some arithmetic calculation for positioning each object using their key values. Counting sort uses the partial hashing technique to count the occurrence of the element in O(1). The most important feature of working with counting sort is that it works with negative elements also. It uses the subroutine to another sorting algorithm. The counting sort is not a comparison-based sorting algorithm and its time complexity is O(n) with space proportional to the range of elements. Therefore, the efficiency of counting sort is maximum if the range of elements is not greater than the number of elements to be sorted.

**Algorithm of Counting**

1. Counting_Sort( array, ele ) // ele is number of elements in the array

2. max = discover the array's biggest element

3. Create a count array of maximum + 1 size and fill it with all 0s.

4. for i = 0 to ele

5. discover the total number of occurrences of each element and save the count in the count array at the index.

6. for i = 0 to max

7. Add the current(i) and previous(i-1) counts to get the cumulative sum, which you may save in the count array.

8. For j = ele down to 1

9. Decrement the count of each element copied by one before copying it back into the input array.

**Implementation in Python**

# Counting sort in Python programming def countingSort(array): size = len(array) output = [0] * size # Initialize count array count = [0] * 10 # Store the count of each elements in count array for i in range(0, size): count[array[i]] += 1 # Store the cummulative count for i in range(1, 10): count[i] += count[i - 1] # Find the index of each element of the original array in count array # place the elements in 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 original array for i in range(0, size): array[i] = output[i] data = [4, 2, 2, 8, 3, 3, 1] countingSort(data) print("Sorted Array in Ascending Order: ") print(data)

**Implementation in C++**

// Counting sort in C++ programming #include <iostream> using namespace std; void countSort(int array[], int size) { // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output[10]; int count[10]; int max = array[0]; // Find the largest element of the array for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) { count[i] = 0; } // Store the count of each element for (int i = 0; i < size; i++) { count[array[i]]++; } // Store the cummulative count of each array for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } // Copy the sorted elements into original array for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Function to print an array 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); }

Counting sort takes O(n+k) time and O(n+k) space, where nn is the number of items we're sorting and k is the number of possible values. We iterate through the input items twiceโonce to populate counts and once to fill in the output array. Both iterations are O(n) time. Additionally, we iterate through counts once to fill in nextIndex, which is O(k) time. The algorithm allocates three additional arrays: one for counts, one for nextIndex, and one for the output. The first two are O(k) space and the final one is O(n) space.

In many cases cases, k is O(n) (i.e.: the number of items to be sorted is not asymptotically different than the number of values those items can take on. Because of this, counting sort is often said to be O(n) time and space.

With this article at Logicmojo, you must have the complete idea of analyzing Counting Sort algorithm.

**Good Luck & Happy Learning!!**