Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the array, and stores these same elements in the auxiliary array. It was developed by Harold H. Seward in 1954.

Complexity table of counting sort

ComplexityBest caseAverage caseWorst case
TimeΩ (n + k)Θ (n + k)O (n + k)
Space  O S(nk)

Where n is the number of the element, and k is the range of the input.

Algorithm of counting sort

Example 1: Suppose we have the following array, which we have to sort.

55418223

Step 1: Find the largest element in the given array.             

Largest element is = 8   5 5 4 1 8 2 2 3  

Step 2: Initialize a new array, and the size of the new array is (Largest + 1).  

Counting Sort in DS

Step 3: Count each element in the given array, and stores the element at their respective index in the count array. For example: If 5 is assigned 2 times to the original array, then 2 will be stored at the 5th position in the count array. If 6 is assigned 0 times, then 0 will be stored at the 6th position in the count array. 

Counting Sort in DS

Step 4: Make the cumulative sum of the elements of the count array. This helps to place the elements in the correct index of the sorted array.  

Counting Sort in DS

Step 5:  This process will be implemented throughout the array.  

Counting Sort in DS
Counting Sort in DS
Counting Sort in DS
Counting Sort in DS
Counting Sort in DS

Counting sort program in C language:

Pin It on Pinterest

Share This