Counting Sort Algorithm


What is Counting Sort Algorithm?

The basic idea is to determine the "rank" of each number in the final sorted array.
Counting Sort uses three arrays:
1.A [1, n] holds initial input.
2.B [1, n] holds sorted output.
3.C [1, k] is the array of integer. 
In which C [x] is the rank of x in A where x ? [1, k]
Firstly C [x] should be  a number of elements of A [j] that is equal to x.

Initialize C to zero
For each term of  j from 1 to n increment C [A[j]] by 1
We set B[C [x]] =A[j]

If there are any duplicates, we decrement C [i] after copying.

Image Reference: Brilliant Maths And Science Wiki

Flow Chart for Counting Sort

Image Reference: Geeks for Geeks

Counting Sort Pseudocode:

Counting Sort (array P, array Q, int k) 1. For i ? 1 to k 2. Then do C [i] ? 0 [ ?(k) times] 3. for j ? 1 to length [A] 4. Then do C[A[j]] ? C [A [j]]+1 [?(n) times] 5. // C [i] now contains the number of elements which is equal to i 6. for i ? 2 to k 7. Then do C [i] ? C [i] + C[i-1] [?(k) times] 8. //C[i] now contains the number of elements which is ? i 9. For for j ? length [A] down to 1 [?(n) times] 10. do B[C[A[j] ? A [j] 11. C[A[j] ? C[A[j]-1

Counting Sort Implementation in Java

class CountingSort { void sort(char arr[]) { int n = arr.length; char output[] = new char[n]; 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 // To make it stable we are operating in reverse order. for (int i = n-1; i>=0; 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]); } }

Output of the above program

Sorted character array is eeeefggkkorss

Solution Worked 0 UpvotesUpvote


Solution Didn't Worked 0 DownvotesDownvote



Play 2048 Game Online

Search Tags

    Algorithm for counting Sort