Java Program to Implement Counting Sort
By Coder Scratchpad on in Java
Sorting is a core concept in programming, and understanding how to organize data efficiently can make a big difference in your applications. One sorting algorithm that is particularly fast and beginner-friendly for specific types of data is Counting Sort. Unlike other sorting methods, Counting Sort doesn’t rely on comparisons. Instead, it counts the number of occurrences of each element and then arranges them in order, making it highly efficient for numbers within a limited range.
In this article, we will explore how to implement Counting Sort in Java in multiple ways, from basic loops to recursion and even handling negative numbers. Java is a versatile programming language, widely used in web development, mobile apps, and enterprise solutions. By learning Counting Sort in Java, beginners can strengthen their understanding of algorithms and improve their problem-solving skills in real-world scenarios.
Table of Contents
Toggle- Program 1: Basic Counting Sort Using Loops
- Program 2: Stable Counting Sort Using Auxiliary Array
- Program 3: Counting Sort Using Recursion
- Program 4: Counting Sort Handling Negative Numbers
- Program 5: Stable Counting Sort for Characters
- Frequently Asked Questions (FAQ)
- Conclusion
Program 1: Basic Counting Sort Using Loops
This first example demonstrates a simple Counting Sort using loops. It’s the standard approach and is perfect for beginners who are learning sorting algorithms for the first time.
public class CountingSortExample1 {
public static void countingSort(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}
int[] count = new int[max + 1];
for (int num : arr) {
count[num]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] numbers = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original Array:");
for(int num : numbers) System.out.print(num + " ");
countingSort(numbers);
System.out.println("\nSorted Array:");
for(int num : numbers) System.out.print(num + " ");
}
}
public class CountingSortExample1 {
public static void countingSort(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}
int[] count = new int[max + 1];
for (int num : arr) {
count[num]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] numbers = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original Array:");
for(int num : numbers) System.out.print(num + " ");
countingSort(numbers);
System.out.println("\nSorted Array:");
for(int num : numbers) System.out.print(num + " ");
}
}
In this program, we first find the largest number to determine the size of the counting array. Each element’s frequency is recorded, and the original array is rebuilt in sorted order. Beginners can clearly see how counting occurrences and placing elements back results in a sorted list.
Program 2: Stable Counting Sort Using Auxiliary Array
Sometimes it’s important to maintain the relative order of equal elements. This version of Counting Sort is stable, which is useful when sorting objects with multiple attributes.
import java.util.Arrays;
public class StableCountingSort {
public static void countingSort(int[] arr) {
int max = arr[0];
int min = arr[0];
for (int num : arr) {
if (num > max) max = num;
if (num < min) min = num;
}
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
for (int num : arr) count[num - min]++;
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
public static void main(String[] args) {
int[] arr = {4, -2, 2, -8, 3, 3, -1};
System.out.println("Original Array:");
System.out.println(Arrays.toString(arr));
countingSort(arr);
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
public class StableCountingSort {
public static void countingSort(int[] arr) {
int max = arr[0];
int min = arr[0];
for (int num : arr) {
if (num > max) max = num;
if (num < min) min = num;
}
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
for (int num : arr) count[num - min]++;
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
public static void main(String[] args) {
int[] arr = {4, -2, 2, -8, 3, 3, -1};
System.out.println("Original Array:");
System.out.println(Arrays.toString(arr));
countingSort(arr);
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(arr));
}
}
Here, we first compute a cumulative count array and then place elements in the output array from right to left. This preserves the original order of equal elements, making the algorithm stable. Beginners can learn how stability is added to a fast algorithm without sacrificing efficiency.
Program 3: Counting Sort Using Recursion
Recursion is a fundamental programming concept, and we can also implement Counting Sort recursively. This example shows a beginner-friendly way to combine counting logic with recursion.
public class CountingSortExample3 {
static int index;
public static void countingSortRecursive(int[] arr, int max) {
int[] count = new int[max + 1];
for (int num : arr) count[num]++;
index = 0;
placeElements(arr, count, 0);
}
private static void placeElements(int[] arr, int[] count, int i) {
if (i >= count.length) return;
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
placeElements(arr, count, i + 1);
}
public static void main(String[] args) {
int[] numbers = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original Array:");
for(int num : numbers) System.out.print(num + " ");
countingSortRecursive(numbers, 8);
System.out.println("\nSorted Array:");
for(int num : numbers) System.out.print(num + " ");
}
}
public class CountingSortExample3 {
static int index;
public static void countingSortRecursive(int[] arr, int max) {
int[] count = new int[max + 1];
for (int num : arr) count[num]++;
index = 0;
placeElements(arr, count, 0);
}
private static void placeElements(int[] arr, int[] count, int i) {
if (i >= count.length) return;
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
placeElements(arr, count, i + 1);
}
public static void main(String[] args) {
int[] numbers = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original Array:");
for(int num : numbers) System.out.print(num + " ");
countingSortRecursive(numbers, 8);
System.out.println("\nSorted Array:");
for(int num : numbers) System.out.print(num + " ");
}
}
In this recursive version, the while loop is combined with a recursive call to handle the counting array. Beginners can practice understanding recursion while seeing the same sorting logic in action. It’s a helpful way to bridge simple loops and recursive thinking.
Program 4: Counting Sort Handling Negative Numbers
Counting Sort works naturally with positive numbers, but it can be adapted to handle negatives. This program demonstrates that adaptation.
public class CountingSortExample4 {
public static void countingSortWithNegatives(int[] arr) {
int min = arr[0], max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
int[] count = new int[max - min + 1];
for (int num : arr) count[num - min]++;
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] numbers = {4, -2, 2, 8, -3, 3, 1};
System.out.println("Original Array:");
for(int num : numbers) System.out.print(num + " ");
countingSortWithNegatives(numbers);
System.out.println("\nSorted Array:");
for(int num : numbers) System.out.print(num + " ");
}
}
public class CountingSortExample4 {
public static void countingSortWithNegatives(int[] arr) {
int min = arr[0], max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
int[] count = new int[max - min + 1];
for (int num : arr) count[num - min]++;
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] numbers = {4, -2, 2, 8, -3, 3, 1};
System.out.println("Original Array:");
for(int num : numbers) System.out.print(num + " ");
countingSortWithNegatives(numbers);
System.out.println("\nSorted Array:");
for(int num : numbers) System.out.print(num + " ");
}
}
By shifting the numbers so that the minimum element maps to zero, Counting Sort can handle negative values efficiently. Beginners can learn how to adapt algorithms to different types of input, making their coding skills more flexible.
Program 5: Stable Counting Sort for Characters
Counting Sort is not limited to numbers. It can also sort characters or strings efficiently. This program sorts a string alphabetically while maintaining stability.
public class CountingSortExample5 {
public static void countingSortString(String str) {
int[] count = new int[256];
char[] output = new char[str.length()];
for (char c : str.toCharArray()) count[c]++;
for (int i = 1; i < count.length; i++) count[i] += count[i - 1];
char[] chars = str.toCharArray();
for (int i = chars.length - 1; i >= 0; i--) {
output[count[chars[i]] - 1] = chars[i];
count[chars[i]]--;
}
System.out.println(new String(output));
}
public static void main(String[] args) {
String text = "javaprogram";
System.out.println("Original String: " + text);
System.out.print("Sorted String: ");
countingSortString(text);
}
}
public class CountingSortExample5 {
public static void countingSortString(String str) {
int[] count = new int[256];
char[] output = new char[str.length()];
for (char c : str.toCharArray()) count[c]++;
for (int i = 1; i < count.length; i++) count[i] += count[i - 1];
char[] chars = str.toCharArray();
for (int i = chars.length - 1; i >= 0; i--) {
output[count[chars[i]] - 1] = chars[i];
count[chars[i]]--;
}
System.out.println(new String(output));
}
public static void main(String[] args) {
String text = "javaprogram";
System.out.println("Original String: " + text);
System.out.print("Sorted String: ");
countingSortString(text);
}
}
This approach converts characters to their ASCII values and sorts them using the counting array. Beginners can see that the same principles of Counting Sort apply beyond numbers, making it versatile for real-world data like names, words, or codes.
Frequently Asked Questions (FAQ)
Counting Sort often brings up questions for beginners, so here are some answers.
Q1: When is Counting Sort faster than other sorts?
Counting Sort runs in linear time when the range of input numbers is small compared to the array size. It can be faster than comparison-based sorts like Bubble Sort or Quick Sort in these cases.
Q2: Can Counting Sort handle negative numbers?
Yes, by adjusting the counting array to map negative numbers starting from zero, you can sort arrays containing negative values efficiently.
Q3: Is Counting Sort stable?
Yes, if implemented with an output array, Counting Sort is stable. This means elements with equal values maintain their original order, which is important in certain applications.
Q4: Can Counting Sort be applied to strings?
Absolutely. By using ASCII values of characters, Counting Sort can alphabetically sort strings efficiently.
Q5: Are there situations to avoid Counting Sort?
Counting Sort is not memory-efficient for large ranges of numbers. If the maximum number is much larger than the array size, it can consume excessive memory and become less practical.
Conclusion
Counting Sort is an efficient and beginner-friendly algorithm that introduces important concepts like counting occurrences, cumulative frequency, and stability. In Java, we can implement it in multiple ways, using loops, recursion, handling negative numbers, and even sorting characters. Each example provides a different perspective on how the algorithm works and helps beginners strengthen their understanding.
By practicing these examples, you can improve your Java skills, enhance your understanding of algorithms, and gain confidence in solving real-world sorting problems. Counting Sort is a perfect stepping stone to more advanced algorithms, so try experimenting with your own datasets and see how versatile it can be!