Updated March 30, 2023
Introduction to Counting sort in java
Counting Sort is an algorithm that plays a pivotal role in any programming language so does Java. The main objective of the counting sort algorithm is to sort out the object collection in accordance with keys that are present as small integers for sorting the algorithms. It mostly operates and performs the count on the key-value pair, presents the positioning of elements as per output sequence. Running time in this sorting is linear in terms of items, and then the difference between the key values lies between maximum and minimum.
Syntax
There is no specific syntax for performing Counting Sort in Java, but there is a logic flow that is applied in the form of algorithm step by step to perform the Counting sort as per the input and is represented as follows :
Class name {
Method name following sorting ()
{
# Find the length of array defined;
#the output character array will have sorted array
#Create a count arr to store count of each element, characters and initialize it 0
#Store count of each character element in the array
#Build output character and write the logic to make it operated in reverse order
#that builds output can now be copied from the previous array to the current
#Make use of the driver code to move and proceed.
}How Counting sort works in Java?
- As mentioned Counting Sort algorithm plays an important role in programming; it works on the sorting of objects present in a collected format and is used for counting the number of elements present that have distinct key and value pair and again is used with the arithmetic counts determining the position of each element present with each key-value having the difference between the minimum and maximum values.
- Running time or time complexity if checked is linear in nature having all the elements in the array and the difference between the minimum and maximum key values, so these elements and sorting technique is suitable in case of direct use where the variations in keys are not significantly greater than elements present with the required key.
- Although there is another algorithm that can support most of the key handling, it is not that efficient as counting sort as per requirements and hashing thus can be substituted with Radix sort to handle the situation of a large amount of key compared to previous.
- Since counting sort uses key and value pair as part of index value into an array, thus it is not considered as a Comparison sort. Also, the lower bound of the comparison sort is not allowed to it.
- Bucket sort also comes undercounting sort only with the same set of task and similar analysis of time, but when compared to counting sort then at that time, bucket sort requires dynamic arrays, linked lists, or a large amount of memory to hold the elements present in the bucket and then counting sort stores only those values which are individual and single number as per bucket.
- There are certain input and output hypothetical sequences that lie with the fact that the input to counting sort consists of a collection of n items where each item has non-negative integer key values for the max value having some value as k. some descriptions of counting sort are the input to sort simply a linear format sequence of integers.
- The output of an array mostly does not consist of major items with some order of key, but its use needs to be checked with respect to the requirement.
- The time complexity with respect to counting Sort comes out to be O (n+l), where n is the number of elements and l is the range for considering the input.
- Also, the auxiliary space comes out to be O(n+l) only.
Example of Counting sort in java
This program demonstrates the counting sort by considering some of the input and output sequence set as part of the sorting in Java.
Code:
public class Counting_Sort_1{
void sort_0(char arr_0[])
{
int n_8 = arr_0.length;
char output_val[] = new char[n_8];
int count_0[] = new int[528];
for (int l_0 = 0; l_0 < 528; ++l_0)
count_0[l_0] = 0;
for (int y_1 = 0; y_1 < n_8; ++y_1)
++count_0[arr_0[y_1]];
for (int l_0 = 1; l_0 <= 526; ++l_0)
count_0[l_0] += count_0[l_0 - 1];
for (int l_0 = n_8 - 1; l_0 >= 0; l_0--) {
output_val[count_0[arr_0[l_0]] - 1] = arr_0[l_0];
--count_0[arr_0[l_0]];
}
for (int l_0 = 0; l_0 < n_8; ++l_0)
arr_0[l_0] = output_val[l_0];
}
public static void main(String []args){
Counting_Sort_1 ob = new Counting_Sort_1();
char arr_0[] = { 's', 'a', 'r', 'c', 's', 'f', 'o',
'i', 'n', 'c', 'a', 'r', 'm' };
ob.sort_0(arr_0);
System.out.print("Sorted_character_array_in_Counting_Sort ");
for (int l = 0; l < arr_0.length; ++l)
System.out.print(arr_0[l]);
}
}Output:
Explanation
In the above example, we have implemented the counting sort in Java where the following steps have been followed for proper execution:
- A class with Selection_Sort_0 is created then following the set of input to the class.
- Once the class is made, then a method has been created for storing the character array that will have a sorted array.
- Creation of count array with the sense of storing the value as an independent entity in the form of key and value pair further it is stored in the form of char as a count.
- Change in the count is required for counting the actual value and the position of the current character in the output array.
- Building the output array with the set of characters to make it stable and operable in reverse order.
- Copying the sorted array to the current array to get the array sorted in some or the other way.
- The Driver code is executed to drive the entire code base further to get the output from the input source.
Conclusion
Counting sort is a type of sorting algorithm which is applied on an array that consists of a range of elements for sorting. The sorting will be based on the key and value pairs that will be present within the array or the difference of the minimum value or the maximum value. Counting Sorting has provided a lot of aid to the developers when the requirement comes for the implementation using integer numbers in bulk.
Recommended Articles
This is a guide to Counting sort in java. Here we discuss How Counting sort works in Java along with the example and output. You may also have a look at the following articles to learn more –
