Counting Sort Implementation in Java
Overview
Counting Sort is a non-comparison-based sorting algorithm that efficiently sorts integers within a specified range. Unlike traditional comparison-based sorting algorithms like Quicksort or Merge Sort, Counting Sort Implementation in Java exploits the specific characteristics of the input elements to achieve linear time complexity.
Here’s a brief overview of how Counting Sort works:
- Counting Occurrences: The algorithm begins by counting the number of occurrences of each unique element in the input array.
- Creating a Counting Array: Based on the counts, it creates an auxiliary array, often called the “counting array,” to store the cumulative count of elements up to each unique value.
- Cumulative Counting Array: The counting array is then modified to represent the cumulative count of elements. This step helps determine the correct position of each element in the sorted array.
- Sorted Array Construction: Using the information from the counting array, a sorted array is constructed by placing elements in their correct positions based on their cumulative counts.
- Copying Back to Original Array: Finally, the sorted array is copied back to the original array, completing the sorting process.
Counting Sort is particularly efficient when the range of possible values in the input array is small compared to the number of elements. Its linear time complexity, O(n + k), where n is the number of elements and k is the range, makes it well-suited for certain scenarios, such as sorting integers within a limited range.
Java Implementation
Counting Sort operates by counting the number of occurrences of each element in the input array and using that information to construct a sorted array. It is especially efficient when dealing with a relatively small range of integer values.
import java.util.Arrays;
public class CountingSort {
public static void main(String[] args) {
int[] array = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original Array: " + Arrays.toString(array));
// Call the sort method to perform Counting Sort
sort(array);
System.out.println("Sorted Array: " + Arrays.toString(array));
}
public static void sort(int[] array) {
int n = array.length;
// Find the maximum element to determine the counting array size
int max = Arrays.stream(array).max().orElse(0);
// Create a counting array to store the count of each element
int[] count = new int[max + 1];
// Populate the counting array with element counts
for (int i : array) {
count[i]++;
}
// Update the counting array to represent the cumulative count
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Create the sorted array based on the counting array information
int[] sortedArray = new int[n];
for (int i = n - 1; i >= 0; i--) {
sortedArray[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// Copy the sorted array back to the original array
System.arraycopy(sortedArray, 0, array, 0, n);
}
}
Understanding the Logic
Counting Array:
- Create a counting array to store the count of each element.
- Populate the counting array with the occurrences of each element in the input array.
Cumulative Count:
- Update the counting array to represent the cumulative count of elements.
- This step helps determine the correct positions of elements in the sorted array.
Sorted Array Construction:
- Create a sorted array based on the counting array information.
- Populate the sorted array by decrementing the count for each element.
Original Array Update:
- Copy the sorted array back to the original array, completing the sorting process.
Example Usage
Consider an example array: {4, 2, 2, 8, 3, 3, 1}
.
Counting Array:
- The counting array would represent the occurrences of each element:
{1, 2, 2, 0, 1, 0, 0, 1}
.
Cumulative Count:
- After updating, the counting array becomes
{1, 3, 5, 5, 6, 6, 6, 7}
.
Sorted Array:
- The sorted array is constructed using the counting array information:
{1, 2, 2, 3, 3, 4, 8}
.
Output:
Original Array: [4, 2, 2, 8, 3, 3, 1]
Sorted Array: [1, 2, 2, 3, 3, 4, 8]
Complexity:
Complexity | Best Case | Average Case | Worst Case |
---|---|---|---|
Time Complexity | O(n + k) | O(n + k) | O(n + k) |
Space Complexity | O(k) | O(k) | O(k) |
Conclusion
Counting Sort is a powerful algorithm for sorting integers within a specific range efficiently. Understanding its implementation in Java provides valuable insights into its application and efficiency.
Latest Posts:
- Merging Two Sorted Arrays in JavaTitle: Merging Two Sorted Arrays in Java Merging two sorted arrays into a single array is a common operation in… Read more: Merging Two Sorted Arrays in Java
- Frequency of Elements in an ArrayTitle: Frequency of Elements in an Array Using Java Counting the frequency of elements in an array is a fundamental… Read more: Frequency of Elements in an Array
- Calculate the sum of diagonals in a matrixTitle: Calculate the sum of diagonals in a matrix In this blog post, we’ll delve into the world of matrices… Read more: Calculate the sum of diagonals in a matrix
- Binary Search in JavaBinary search is a powerful algorithm used to efficiently find a target value in a sorted array. In this blog… Read more: Binary Search in Java
- Removing Duplicate Elements in Array using JavaRemoving Duplicate Elements in Array using Java Arrays are fundamental in Java, but duplicate elements can clutter your data. In… Read more: Removing Duplicate Elements in Array using Java
- Transpose a 2D Array in JavaTitle: Transpose a 2D Array in Java In Java, transposing a 2D array involves converting its rows into columns and… Read more: Transpose a 2D Array in Java