Counting Sort      

Linear Sorts: Counting Sort


What is Counting Sort Algorithm?




Iterating through the input, counting the number of times each item appears, and utilizing those counts to compute each item's index in the final, sorted array is how counting sort works.

Consider a given array that needs to be sorted. First, you’ll have to find the largest element in the array and set it to the max.Step 1.

To store the sorted data, you will now initialize a new count array with length "max+1" and all elements set to 0.Step 2.

Later, as shown in the figure, you will store elements of the given array with the corresponding index in the count array.Step 3.

Now, you will change the count array by adding the previous counts to produce the cumulative sum of an array, as shown below:Step 4.

Because the original array has nine inputs, you will create another empty array with nine places to store the sorted data, place the elements in their correct positions, and reduce the count by one.Step 5.

As a result, the sorted array is:Step 6.




To learn more about Counting Sort: Counting Sort Algorithm: Overview, Time Complexity & More.