Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
Java
// Java implementation of Counting Sortimport java.io.*;public class CountingSort { void sort(char arr[]) { int n = arr.length; // The output character array that will have sorted arr char output[] = new char[n]; // Create a count array to store count of individual // characters and initialize count array as 0 int count[] = new int[256]; for (int i = 0; i < 256; ++i) count[i] = 0; // store count of each character for (int i = 0; i < n; ++i) ++count[arr[i]]; // Change count[i] so that count[i] now contains actual // position of this character in output array for (int i = 1; i <= 255; ++i) count[i] += count[i - 1]; // Build the output character array for (int i = 0; i < n; ++i) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } // Copy the output array to arr, so that arr now // contains sorted characters for (int i = 0; i < n; ++i) arr[i] = output[i]; } // Driver method public static void main(String args[]) { CountingSort ob = new CountingSort(); char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's' }; ob.sort(arr); System.out.print("Sorted character array is "); for (int i = 0; i < arr.length; ++i) System.out.print(arr[i]); }}/*This code is contributed by Rajat Mishra */ |
Output:
Sorted character array is eeeefggkkorss
Time Complexity: O(n+k) where n is the number of elements in the input array and k is the range of input.
Auxiliary Space: O(n+k)
Please refer complete article on Counting Sort for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
