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

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:

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