Counting Sort Algorithm with implementation in Java and Python

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

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote

        


Comments



Search


Play 2048 Game Online

Play Duckhunt Online
Search Tags

    Algorithm for counting Sort

    Counting Sort python

    Counting Sort Java Program

    java code for counting sort