Counting Sort Algorithm with implementation in Java and Python

[7263 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:

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

                 





Comments





Search
Get Answers to your Programming Questions


Recommended Deals ends in








Quiz For You:

Search Tags

    Algorithm for counting Sort

    Counting Sort python

    Counting Sort Java Program

    java code for counting sort