What is counting sort

#1

I don’t understand this is not in any video lecture

#2

counting sort uses range according to input constraints 0<=Ai<=10^6 this is huge so hot to di it

#3

please help I am not getting it

#4

Hi Arvind,Sorry for late reply.
Counting Sort works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Let us understand it with the help of an example.

For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2

  1. Take a count array to store the count of each unique object.
    Index: 0 1 2 3 4 5 6 7 8 9
    Count: 0 2 2 0 1 1 0 1 0 0

  2. Modify the count array such that each element at each index
    stores the sum of previous counts.
    Index: 0 1 2 3 4 5 6 7 8 9
    Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in
the output sequence.

  1. Output each object from the input sequence followed by
    decreasing its count by 1.
    Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
    Put data 1 at index 2 in output. Decrease count by 1 to place
    next data 1 at an index 1 smaller than this index.

Coming to the Code Part:

  1. Create a count array to store count of individual characters and initialize count array as 0.
  2. Store count of each character.
    3 . Change count[i] so that count[i] now contains actual position of this character in output array.
    4.Make another Output Array,which we need to store our sorted Array Characters.
  3. Build the output character array.
  4. Print this Sorted Output Character Array.
    Thankyou.
#5

thanks for your detailed reply , I was asking about the input constraint for this problem because it is huge for counting sort to be effective

#6

@radhagovinda008
The Counting Sort has a time complexity of O(n+k) where n is the number of elements in Array and k is the range of elements.
As you are saying for n=10^6 will it work or not?
Yes,It will work as Substituting n=10^6 in above O(n+k) will result in roughly 10^6 Operations per second.
And till 10^8 operations per second are accepted.
Thankyou.

#7

ok thank you for the details