Counting sort..............

#1

this algo not covered in videos, I check it on geeeksforgeeks, but I don’t understand

#2

Hi Dhruv,
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.

3 .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.
Build the output character array.
Print this Sorted Output Character Array.
Thankyou.

#3

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

#4

whats this ? i not understand

#5

pls elaborte with example

#6

@Dhruv-Goyal-449223618988467
Lets go step-wise,
Are you having correct understanding till point 2 ?If not,
Once you are cleared with the first 2 points i will elaborate more on 3.
Also consider this:

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.