Counting sort algorithm Java
Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.
V článku sa dozvieš:
There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.
To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and implement them in Java.
Today we will look at counting sort.
So far, we have discussed:
- Sorting algorithms: Introduction to data sorting
- Bubble sort
- Comb sort
- Big O notation: analysis of algorithms’ time and space complexity
- Selection sort
- Insertion sort
What is counting sort
So far we have discussed algorithms that compare elements and produce a sorted output based on that comparison. Counting sort is the first non-comparison-based sorting algorithm we’re introducing.
Counting sort is an integer-stable sorting algorithm based on counting objects with different key values to determine their position in the output sequence. It should only be used in situations where the variance of the maximum and minimum key values is relatively small compared to the number of elements on the input. This algorithm is often used as an auxiliary routine in the radix sort.
Counting sort step by step
The counting sort algorithm is suitable when we have many elements with integer keys, ideally repeating from a relatively small range (max – min), then we can use this relatively efficient algorithm to sort the input elements. It works by counting the occurrences of each key and storing them in an auxiliary array. This is then transformed into an array of indices with the resulting positions of each element. It is then used to map the elements from the input vector to the output vector.
The best way to understand how the algorithm works is through a practical example in Java, which we will implement.
Counting sort advantages
- Easy to implement
- Fast and efficient when the range of k is small compared to the number of elements in the input n,
- Stable
Counting sort disadvatages
- Only works with integer keys
- Inefficient for large ranges
Counting sort time complexity
| Algorithm | Method | Time Complexity | Memory | Stable | ||
| worst | average | best | ||||
| Counting sort | counting | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
The variable k is the number of elements in the array to be counted, mathematically k = (maximum – minimum + 1). Since we iterate over the input array of elements, we get a time complexity of O(n). Iterating over the auxiliary array contributes a complexity of O(k), so the total time complexity is O(n+k).
Storing k elements in an auxiliary array in memory results in a counting sort space complexity of O(k).
Counting sort animation, visualization, gif
The counting sort visualization looks like this:
Source : https://commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Counting sort animation can be found on this page.
Counting sort Java implementation
We will now show a simple implementation of the counting sort algorithm in Java.
CountingSort.java
package sorting;
public class CountingSort {
private int min, max;
public void sort(int data[])
{
// Don't sort if there are no elements
if(data.length == 0)
return;
// Create ouput array
int[] output = new int[data.length];
// Find min and max value in 1 loop
min = data[0];
max = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] < min) {
min = data[i];
} else if (data[i] > max) {
max = data[i];
}
}
// Create count array
int k = max - min + 1;
int[] count = new int[k];
System.out.println("min = " + min + ", max = " + max +
", size (n) = " + data.length + ", range (k) = " + k);
// Count occurrences of elements
for (int i = 0; i < data.length; i++) {
count[data[i] - min]++;
}
System.out.print("Count array: ");
printArray(count);
// Transform counts to positions
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
System.out.print("Transformed count array: ");
printArray(count);
// Map the elements from input to output based on count indexes
// Do it backwards
for (int i = data.length - 1; i >= 0; i--) {
output[count[data[i] - min] - 1] = data[i];
count[data[i] - min]--;
}
// Copy the elements from output back to original array
for (int i = 0; i < data.length; i++) {
data[i] = output[i];
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}The algorithm consists of the following steps, which we will explain briefly:
Check empty array
If the array is empty, there is nothing to sort.
Finding the minimum and maximum values
Let’s find out the range of values of min and max.
Creating and initializing a counting array
The size of the count array is the difference between the maximum and minimum value plus one to cover the entire range of values.
Counting the occurrences of elements
For each element in the input array, the value at the corresponding index in the counting array is incremented by one.
Transformation to accumulated counts
Each element in the counting array is updated to the sum of all previous values, which determines the final positions of the elements in the output array.
Placement of elements in the output array
The input array is traversed backwards (to ensure stability) and elements are placed in the output array based on the values in the counting array, decrementing the counting array index by 1 after each element placement.
Copy the output back to the original array
The sorted elements from the output array are copied back to the original array.
Main.java
import sorting.CountingSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 4, 2, 4, 2, 1, 1, 1, 7, 6, 3, 5, 5 };
CountingSort countingSort = new CountingSort();
System.out.print("Input: ");
countingSort.printArray(dataToSort);
countingSort.sort(dataToSort);
System.out.print("Sorted: ");
countingSort.printArray(dataToSort);
}
}The output of this counting sort example is:
Counting sort Java code example
We have prepared the files with the above example as code that you can run directly in Java. Download the Java counting sort code here.
If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers!
