Counting Sort Algorithm

(666 Views)


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.
	
countingsort

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



Comments



Search

Play 2048 Game Online

Search Tags

    Algorithm for counting Sort