EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Counting Sort Algorithm
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search
    • Stock Span Problem

Counting Sort Algorithm

Counting Sort Algorithm

Definition of Counting Sort Algorithm

This is one of the techniques to sort the array elements; it performs sorting by calculating the number of occurrences of a particular element in an array. It maintains a separate array to count the number of occurrences of the element; after that, it performs sorting by mapping the count. We can write the logic for Counting sort in any language, but before that, we should have a clear understanding of the algorithm to start with It is easy to understand but take a while to get clarity on how it works internally. We will see the algorithm written in Java language. This algorithm first counts the unique elements inside an array then performs the sorting; hence the name is the Counting sort algorithm. In this coming section of the tutorial, we will see the more detailed internal working of this algorithm to get a better idea and usage in our program for beginners.

Counting sort algorithm

As we have already known that it is a sorting algorithm based on the counting of the unique element; in this section, we will first see the algorithm itself then one practice sample example to understand its working in detail. Let’s get started

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Algorithm:

1) Start
2) Count array to maintain the count of the unique elements inside the input.
3) Modify the count array to contain the sum of the previous counts.
4) map data t the array and decrees the count by 1.

Above is the basic idea to create and understand the counting sort algorithm, but now we will see how it works with a sample array example in detail to get more about the Count sort algorithm. This sample example will make it easy to understand, so let’s get started;

Input array : 4, 3, 2, 5 ,4, 3, 5, 1, 0, 2, 5

1) Now, we have this input array which we want to sort b applying the courting sort technique. Here we have taken the example of an array within the range of 0 to 5 for better understanding.

2) Now, we will create one counting array, which will contain the occurrence of all the unique elements from the input array. Let’s suppose here we have ‘4’, which is occurring two times in the input array, so we will place the count as the value inside the array on the specified array. So the counting array will range from 0 to 5; let’s understand this,

count array index : 0, 1, 2, 3, 4, 5
value at each index : 1, 1, 2, 2, 2, 3

In the above lines, we have counted the number of occurrences, which show as value, here 0 occur once, 1 occur 1, and so on. For better understanding, we have 4, which occurred 2 times in the array, so its value would be 2 here.

3) Now, in this step, we will determine how many elements are less than or equal to the elements present inside the input array.

4) Now, we will take sum of all the previous values and put it inside the count array like below;

e.g. :

index : 0, 1, 2, 3, 4, 5

before: 1, 1, 2, 2, 2, 3

after : 1, 2, 4, 6, 8, 11

As you can see in the above example we are trying to add the previous all elements and get the sum as the value for that element. For example :
0 = 0;
1 = 0+1;
2 = 1+1+2;
3= 1+1+2+2;
4= 1+1+2+2+2
5= 1+1+2+2+2+3

In this, we way, we are going to design our count array and place the new values at the specified index.

5) Now iterate the input array in the reverse order, and we will use the count array to sort the element.

6) now, each of the elements from the count array that counts [i]-1 is going to represent the location of an element in the sorted array.

7) Now, we will decrement the count[i] and repeat the above process to place the element inside the sorted array.

8) At the end, we will get the sorted array as a result.

Examples

1) In this example, we are trying to sort the crat array given, and we are writing the logic following the counting sort algorithm that we discussed in the above points. This is a sample piece of code you can also create to sort the integer array with some modification in the below code, copy this program and run it in your editor to see the output.

Example #1

package com.interview.practise;
public class CountingSortDemo {
void sort(char myarray[])
{
int arrlength = myarray.length;
char resultOutput[] = new char[arrlength];
int countarray[] = new int[256];
for (int i = 0; i < 256; ++i){
countarray[i] = 0;
}
for (int i = 0; i < arrlength; ++i){
++countarray[myarray[i]];
}
for (int i = 1; i <= 255; ++i){
countarray[i] += countarray[i - 1];
}
for (int i = arrlength - 1; i >= 0; i--) {
resultOutput[countarray[myarray[i]] - 1] = myarray[i];
--countarray[myarray[i]];
}
for (int i = 0; i < arrlength; ++i){
myarray[i] = resultOutput[i];
}
}
public static void main(String args[])
{
System.out.println("Demo for counting sort in JAVA !!");
CountingSortDemo ob = new CountingSortDemo();
char myarray[] = { 'h', 'e', 'l', 'l', 'o', 'l', 'e', 'a', 'r', 'n', 'e', 'r' };
System.out.println("calling inbuild method");
ob.sort(myarray);
System.out.print("After sorting array is ::: ");
for (int i = 0; i < myarray.length; ++i){
System.out.print(myarray[i]);
}
}
}

Output:

Counting Sort Algorithm 1

Complexity: Let’s see the time complexity for the counting sort algorithm is:

Time Complexity : O(n+k)

Note: we cannot sort negative values by using this algorithm because we don’t have a negative index to maintain the occurrence in the count array.

Conclusion

It is easy to sort the array elements, but we have to maintain an auxiliary array to get the occurrence of the unique elements from the input array; once you get the basic idea and understand of its internal working, then it is easy to implement and use.

Recommended Articles

This is a guide to Counting Sort Algorithm. Here we discuss the Definition, How to internal working of Sort Algorithm? examples with code implementation. You may also have a look at the following articles to learn more –

  1. Bubble Sort Algorithm
  2. Sorting Algorithms in Python
  3. Sorting Algorithms in JavaScript
  4. Sorting Algorithms in Java
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (10 Courses, 8+ Projects)4.7
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more