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:
countingSort(array, size)
max <- find largest element in array
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique element and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 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
Counting Sort Implementation in Python :
def counting_sort(A, digit, radix):
#"A" is a list to be sorted, radix is the base of the number system, digit is the digit
#we want to sort by
#create a list B which will be the sorted list
B = [0]*len(A)
C = [0]*int(radix)
#counts the number of occurences of each digit in A
for i in range(0, len(A)):
digit_of_Ai = (A[i]/radix**digit)%radix
C[digit_of_Ai] = C[digit_of_Ai] +1
#now C[i] is the value of the number of elements in A equal to i
#this FOR loop changes C to show the cumulative # of digits up to that index of C
for j in range(1,radix):
C[j] = C[j] + C[j-1]
#here C is modifed to have the number of elements <= i
for m in range(len(A)-1, -1, -1): #to count down (go through A backwards)
digit_of_Ai = (A[m]/radix**digit)%radix
C[digit_of_Ai] = C[digit_of_Ai] -1
B[C[digit_of_Ai]] = A[m]
return B
#alist = [9,3,1,4,5,7,7,2,2]
#print counting_sort(alist,0,10)
Complexity of Counting Sort Algorithm:
Counting sort has a O(k+n)O(k+n) running time.
The first loop goes through AA, which has nn elements. This step has a O(n)O(n) running time. The second loop iterates over kk, so this step has a running time of O(k)O(k). The third loop iterates through AA, so again, this has a running time of O(n)O(n). Therefore, the counting sort algorithm has a running time of O(k+n)O(k+n).
Counting sort is efficient if the range of input data, kk, is not significantly greater than the number of objects to be sorted, nn.
Counting sort is a stable sort with a space complexity of O(k + n)O(k+n).