I dont understand the way he explained counting sort in the video

#1

can someone clarify how he is calculating the counting sort part

#2

hello @shibangi

counting sort is simple sorting algorithm based on frequency.

let say u have arrays with elements in range [0…c]

so what u can do is first store frequency of each elemnts in some array .
and iterate from smallest number to largest number and print each number equal to its frequency times.

for eg.
[1,3,1] consider this array. here elements are in range [0…3]
so what we do is we calculate frequcny of each elements
0-> 0 ( 0 comes 0 times)
1->2 ( 1 comes 2 times)
2-> 0 (2 comes 0 time)
3->1(3 comes 1 times)

now iterate from 0 to 3 and print each number equal to its frequency times.
so finally we will get this.
1 1 3

#3

if i print it equal to frequency times I would need another loop right? like for within for ? doesnt that increase the complexity and overall defeat the purpose

#4

no it will not increase the complexity .
lets say c1,c2,c3…cn are the counts of frequency.
then c1+c2+c3+…+cn=n right?
that means in total ur algo works only O(n) .

#5

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.