Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45
Everything You Need to Know About the Counting Sort Algorithm

Harold Seward discovered Counting Sort in 1954. Counting sort is a linear sorting algorithm with asymptotic complexity O(n+k). The Counting Sort method is a fast and reliable sorting algorithm. Counting sort, unlike bubble and merge sort, is not a comparison-based algorithm. It avoids comparisons and takes advantage of the array's O(1) time insertions and deletions. 

The Counting Sort algorithm sorts keys that are small integers and fall inside a particular range. It works by calculating the number of elements with each unique key value. After that, it performs specific mathematical calculations to sort each key value.

What Is a Counting Sort Algorithm?

  • Counting sort is an integer sorting algorithm used in computer science to collect objects according to keys that are small positive integers.
  • It works by determining the positions of each key value in the output sequence by counting the number of objects with distinct key values and applying prefix sum to those counts.
  • Because its running duration is proportional to the number of items and the difference between the maximum and minimum key values, it is only suited for direct usage when the number of items is not much more than the variation in keys.
  • It's frequently used as a subroutine in radix sort, a more efficient sorting method for larger keys.

In the next section, you will discover the working procedure of the counting sort algorithm after knowing what it is.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

Working on Counting Sort Algorithm

Iterating through the input, counting the number of times each item appears, and utilizing those counts to compute each item's index in the final, sorted array is how counting sort works.

  • Consider a given array that needs to be sorted. First, you’ll have to find the largest element in the array and set it to the max.

example-of-counting-sort-algorithm

  • To store the sorted data, you will now initialize a new count array with length "max+1" and all elements set to 0.

example-of-counting-sort-algorithm

  • Later, as shown in the figure, you will store elements of the given array with the corresponding index in the count array.

example-of-counting-sort-algorithm2

  • Now, you will change the count array by adding the previous counts to produce the cumulative sum of an array, as shown below:

example-of-counting-sort-algorithm3

  • Because the original array has nine inputs, you will create another empty array with nine places to store the sorted data, place the elements in their correct positions, and reduce the count by one.

example-of-counting-sort-algorithm5

  • As a result, the sorted array is:

example-of-counting-sort-algorithm6

Pseudo Code and Algorithm of Counting Sort Algorithm

The Pseudocode of Counting Sort

  • Iterate through the input array to find the highest value.
  • Declare a new array with the value 0 and a size of max+1.
  • Count each element in the array and increment its value in the auxiliary array generated at the corresponding index.
  • Add current and previous frequency to the auxiliary array to find the cumulative sum.
  • The cumulative value now represents the element's actual position in the sorted input array.
  • Begin iterating through the auxiliary array from 0 to max.
  • Put 0 at the corresponding index and reduce the count by 1, which will indicate the element's second position in the input array if it exists.
  • Now put the array you got in the previous step into the actual input array.

The Algorithm of Counting

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

max <- discover the array's biggest element

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

for i = 0 to ele

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

for i = 0 to max

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

For j = ele down to 1

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

After learning pseudocode and the counting sort method, you will now look at its complexity in this article.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

The Complexity of the Counting Sort Algorithm

Counting Sort Time Complexity

  • It takes time to discover the maximum number, say k.
  • Initializing the count array will take k seconds.
  • k times to preserve the count array.
  • Now you will do the actual sorting by iterating over the input array linearly.
  • Because all preceding stages are constant regardless of the input array, the best, average, and worst time complexity will remain constant.

Best Case

When all items are in the same range, or when k is equal to 1, the best case time complexity occurs. In this scenario, counting the occurrences of each element in the input range takes constant time, and finding the correct index value of each element in the sorted output array takes n time, resulting in total time complexity of O(1 + n), i.e. O(n), which is linear.

Worst Case 

The worst-case scenario for temporal complexity is skewed data, meaning that the largest element is much larger than the other elements. This broadens the range of K.

Because the algorithm's time complexity is O(n+k), when k is of the order O(n^2), the time complexity becomes O(n+(n2)), which essentially lowers to O(n^2 ). Where k is of the order O(n^3), the time complexity becomes O(n+(n^3)), which essentially lowers to O(n^3). As a result, the time complexity increased in this scenario, making it O(k) for such big values of k. And that's not the end of it. For larger values of k, things can get significantly worse.

As a result, the worst-case time complexity occurs when the range k of the counting sort is large.

Average Case 

To calculate the average case time complexity, fix N and take various values of k from 1 to infinity; in this scenario, k computes to (k+1/2), and the average case is N+(K+1)/2. However, because K approaches infinity, K is the essential element. Similarly, varying N reveals that both N and K are equally dominating, resulting in O(N+K) as the average case.

Counting Sort Space Complexity

You employed an auxiliary array C of size k in the above procedure, where k is the maximum element in the given array. As a result, the Counting Sort algorithm has an O space complexity (k).

The Complexity of Space: O (k)

The greater the range of elements in a particular array, the greater the space complexity; thus, counting sort's space complexity is terrible if the range of integers is very big, as an auxiliary array of that size must be created.

You will now compare counting algorithms with various sorting methods in this tutorial.

Comparison With Other Sorting Algorithms

  • When the length of the input list is not substantially smaller than the largest key value, k, in the input array, the counting sort has a running time of O(n). In contrast, any comparison-based sorting algorithm takes O(n (log n)) comparisons.
  • In circumstances where the range of input elements is comparable to the number of input elements, counting sort is particularly efficient since it accomplishes sorting in linear time, which might be an advantage over other sorting algorithms like quicksort. When rapid sort takes O(n2) time in the worst scenario, counting sort only takes O(n) time if the range of elements is not too vast.
  • The majority of sorting algorithms run in quadratic time (O(n2), except the heap, and merge sort, which runs in time (O(n log n). The only sorting method that works in linear time is counting sort.
  • Because no items are compared, it is superior to comparison-based sorting approaches.
  • Because counting sort is good for sorting well-defined, finite, and tiny numbers, it can be used as a subprogram in other sorting algorithms like radix sort, which is suitable for sorting numbers with a wide range.

Moving ahead in this article, you will look now at several uses of the counting sort algorithm. 

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Applications of Counting Sort Algorithm

  1. If the range of input data is not much bigger than the number of objects to be sorted, counting sort is efficient. Consider the following scenario: the data is 10, 5, 10K, 5K, and the input sequence is 1 to 10K.
  2. It isn't a sorting system based on comparisons. It has an O(n) running time complexity, with space proportional to the data range.
  3. It's frequently used as a subroutine in other sorting algorithms, such as radix sort.
  4. Counting sort counts the occurrences of the data object in O using partial hashing (1).
  5. The counting sort can also be used with negative inputs.

Finally, in this tutorial, you will implement code for counting sort.

Code Implementation of Counting Sort Algorithm

#include <stdio.h>  

#include<stdlib.h>

#include<conio.h>

void counting_sort(int Array[], int k, int n)  

{  

    int i, j;  

    int Array1[10], Array2[100];  

    for (i = 0; i <= k; i++)  

        Array2[i] = 0;  

    for (j = 1; j <= n; j++)  

        Array2[Array[j]] = Array2[Array[j]] + 1;  

    for (i = 1; i <= k; i++)  

        Array2[i] = Array2[i] + Array2[i-1];  

    for (j = n; j >= 1; j--)  

    {  

        Array1[Array2[Array[j]]] = Array[j];  

        Array2[Array[j]] = Array2[Array[j]] - 1;  

    }  

    printf("Sorted array is : ");  

    for (i = 1; i <= n; i++)  

        printf("%d ", Array1[i]);  

}  

int main()  

{  

    int n, k = 0, Array[15], i;  

    printf("Enter the number of elements : ");  

    scanf("%d", &n);  

    printf("\nEnter the elements which are going to be sorted :\n");  

    for (i = 1; i <= n; i++)  

    {  

        scanf("%d", &Array[i]);  

        if (Array[i] > k) {  

            k = Array[i];  

        }  

    }  

    counting_sort(Array, k, n);  

    printf("\n");  

    return 0;  

}  

Output

output-of-counting-sort-algorithm-code.

With this, you have come to an end of counting sort algorithm articles.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

In this tutorial, you learned what a counting sort algorithm is and some applications and code implementations of the counting sort algorithm.

The Post Graduate Program in Full Stack Web Development from Simplilearn offered in collaboration with Caltech CTME will be ideal for you if you want a more comprehensive study that goes beyond Data Structure and algorithms and covers the most in-demand programming languages and skills today. It's time to get out there and explore.

Do you have any questions about this Counting Sort Algorithm tutorial? Please leave them in the comments section at the bottom of this page if you have any. Our experts will respond as quickly as possible!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.