Count Sort | C++ Placement Course | Lecture 20.1

[@rutvikrana512]

Counting Sort:- Pros: -Time Complexity O(N) - Compareless sorting Cons: -Limited Usage i.e for int -Memory Consuption Uses: - Sort numbers - find counts of letter from string - remove duplicate from string - find kth smallest or biggest element from array within O(N) time. HAPPY LEARNING :)

[@rajmhatre20]

is your code working? if yes can you share the code here

[@maulikshah28]

@@rajmhatre20 Here you go brother: #include using namespace std; void countSort(int arr[], int n){ int k=arr[0]; for(int i=0; i arr[i]; } countSort(arr, n); // Printing for(int i=0; i

[@celiafernandes9084]

Thanks for enlightening

[@johnwick-m4m]

@@maulikshah28 Your code doesn't work

[@synergy_944]

@@maulikshah28 .

[@maulikshah28]

The people who come up with these ideas of sorting algorithms are true legends How can they think so far

[@vinayakd4444]

So true!

[@kuldeeprane1469]

yes bro

[@CarlJohnson-cb9xm]

Fuking legends

[@shreechatane9215]

Voice of the instructor is so sweet😁

[@ravikumaryadav4735]

Yha to padh le bhai .

[@mousinmulani6054]

😂

[@jamespottex5197]

@@ravikumaryadav4735 sahi kaha

[@AvidWanderlust]

Padh le chutiye

[@Thee_Beyonder]

@@ravikumaryadav4735 😂😂😂

[@anuragtyagi1111]

When God come to help poor students ❤️

[@sahillabhshetwar2739]

emo boy

[@shailendramaheshwari5471]

if(! willing to learn ) { return poor ; } else { return rich; }

[@radhikaagarwal5502]

Salute to the team🇮🇳! You all are really helping lots of students and has made education , fun to learn with easy explanation

[@ayushgarg7609]

ig, the size of count array could be k+1 and terminating condition of loop should also be (i

[@chinmay_0518]

Variable size cannot be given to array, to use variable size some other concepts are required

[@DawoodRizwan-k7f]

You explaining so good...❤❤❤♥♥

[@mohammadrafi895]

We can create a count array of size (k+1) instead of size 10.

[@Ace-ex9gg]

no

[@mohammadrafi895]

@@Ace-ex9gg Then explain the reason. Saying just 'no' doesn't contradict my statement.

[@ankitwaghmare4007]

The best things happen for students in 2020 is Aman bhaiya and his team come with this teaching facilities ....thank you bhaiya ..... Definately we will make you proud ...just wait ❤️❤️❤️❤️❤️❤️

[@karanjaiswal4682]

dynamic array can be allocated : int* count = new int [ k ];

[@deveshdubey6776]

Thanks bro

[@deveshdubey6776]

Why mam said we can't dynamically allocate memory to count array?

[@karanjaiswal4682]

@@deveshdubey6776 don't know why

[@swostikpati7505]

Why did ma'am assign the size of count array as 10. Won't it cause problems if the actual size is greater than 10?

[@karanjaiswal4682]

@@swostikpati7505 thats why I provided the code for dynamic array allocation

[@anirudh3799]

Bhai apni kaksha channel pe please biology daaalde yaar.Biology ke liye hee sab se zyada zarurat hai animation kaaaaa

[@user-gt8ic3ti6l]

why we need to find the maximum element of an array while after we initialise the count array size 10.

[@dhruvchokshi8805]

it can be sorted in javascript by performing this: arr.sort(function(a,b){return a-b})...this will return the same output

[@KumarSahil78]

This is normal sorting, in java and C++ also have these but the count sort is different.

[@AliShair-f7q]

If you create an array on the heap, such as with int* arr = new int[n]; --> the time complexity is O(n). If you create an array on the stack, such as with int arr[n]; --> the time complexity is O(1).

[@uttamkarmakarece3534]

Time complexity explained in only 2 minutes 😑...it should be explained in details But all over I love this playlist❤️

[@parthapratimghose173]

The trick I did is create Madeleine plus 1 as size of counter array that will solve future memory overflow

[@aniketmani7502]

These sorting algorithms are really great. But still, you forgot about some legendary sorting techniques. 1. Bogo Sort 2. BogoBogo Sort 3. Miracle Sort 4. The Schrodinger's Sort

[@divyam69]

doo bee dooo beee dooo beee

[@ChandanJobanputra]

Dont know why but my code is not giving any output Plz help

[@rajiv-59]

great work mam .............

[@extremesatyaiitjeeair1980]

// I think the final procedure (output array) is better in my idea void countSort(int a[],int n){ int k=a[0]; for(int i=1;i

[@streetfood6183]

Aman bhaiya... Unacademy plus IIT JEE subscription lene ke Baad kya... Hame class 11 Pura padhne k baad class 12 shuru hoga... Ya Phir dono parallel chalenge?

[@marmikprajapati6681]

What if there are negative numbers in array? We can't use count array in that case!!

[@heyitsanmolj]

well, that's just not true. They have mentioned this before in some other video, you gotta use your brain tho. Make an array of length, -min(arr)+max(arr)+1 in case of negative numbers, and you can still do this!

[@mayankbhardwaj3443]

Hlo sir Web design/web development ke course kabb aayenge🙄🙄🙄 Plz upload fast...i want to learn that🙏❤️

[@kartikarora3521]

Bro if you want to learn it then I would recommend you to go to Mozilla Developer Network(aka MDN), it has open source content for learning web development/front-end development and it is made by Mozilla(The organisation that made Firefox Browser). And Bhiya will not upload web design because web design is related to graphic design it does not include coding. Front-end includes coding, which focus on coding the design and ui/ux made by a graphic designer. Web design and front-end are completely different

[@mayankbhardwaj3443]

@@kartikarora3521 thx for the information 😉❤️

[@maulikshah28]

If you really want to learn, then you can but Angela Yu 's Web Development course on udemy. It is really not a bad investment for about 450 rupees I am also learning from it. I highly recommend it

[@mayankbhardwaj3443]

@@maulikshah28 lol...why did u buy it😂😂....i downloaded it free ....😂😂😂want link?? Tell me 😂😂

[@maulikshah28]

@@mayankbhardwaj3443 really? How, tell me

[@rishigupta9680]

i have doubt ki jab ki agr jab extra output array lena hi hai to direct count wale array se kyun nhi sort kr skte index ko padkdo or uski value ko tab tak push kro jab tak wo zero na ho jaye

[@harshwasnik7636]

Ohho... Wo last me "byee".. Maje aa gye

[@irannapatil7050]

up to date i fallow this course and i feel and i know competitor of this course is not available on todays market.

[@harsh461]

My Code School is still the best

[@dheerajbisht4096]

Then u haven't seen the market yet

[@harsh461]

@@dheerajbisht4096 Bhai tu thapar sa ha kya?

[@dheerajbisht4096]

@@harsh461 no bro, ait pune

[@irannapatil7050]

@@dheerajbisht4096 tu hi bol bhai kaha pe hai isse accha

[@mohitrathaur9670]

apka program nahi samagha pa rahe

[@hustlewithVaibhav]

Thank you didi🙏

[@himanshudawande360]

I would be very happy if the Apna college team could reply to us and solve our doubts because sometimes even searching a lot also doesn't solve the doubts . Or if possible please explain the things like why are you declaring this variable and why are you adding it etc in the video itself. THANK YOU the course is awesome

[@ketangupta221]

I don't understand why we need to recursively add all the array elements for getting sum of elements till its previous elements. And then do that extra work of checking each number subtracting it and then putting it in array. We could have just taken elements from the count array which we had formed and just put those numbers in the array in ascending order according to their position in count array and their frequencies.

[@lasbutious116]

I have the same doubt. why make something simple so complicated?

[@riyanshkhandelwal305]

What if there is any negative element in an array? How we will store it in count array? And I also think that size of the count array is one greater than the maximum element in an array arr.

[@maulikshah28]

This code will not work if there are negative elements

[@manishmalhotra5883]

May use map then

[@sourabhchoudhary7289]

can we create count array of size k+1(k=max element in array) i.e. count[k+1]?

[@harpic949]

Same doubt

[@prince-kc6gq]

working for k+1 but dont know whether it is logically correct or not

[@aakashthakre244]

Same doubt and also mam ne k kyu nhi liya 10 kyu liya wo reason bhi nhi samjha 😭

[@sourabhchoudhary7289]

@@aakashthakre244 I thik max+1 would work

[@devjoshi7062]

@@aakashthakre244 Array size + 1 is the way to go for this algorithm as it gives extra breathing space for us to store numbers

[@snehilsinha4689]

I think the size of the count array should be k+1 and not k. I even tried coding it out and it works for k+1 but not for k. Please confirm this once. 🙏

[@suhasshenoy4541]

yes because indicies start from 0 and kth index will be k+1 th element

[@mayurschittaragi]

I had the exact same doubt and was confused for a long time.. Thanks for clearing.😊

[@snehilsinha4689]

@@mayurschittaragi pleasure helping 😊

[@moonalexfeneba6944]

I think you can also take n, As when we put the value of the max element in the array, but in our array, we have many repetitions For example in this question max element is 6 but the no. Of element is 9=n-1 so our loop will work fine if we use i

[@simransaini9079]

exactly you solved my problem

[@mrwordpress6676]

Thanku urvi goel ma'am

[@chahitbhardwaj3075]

Didi yeh batao ki yeh sabhi algorithm humko yaad rakhna hoga kya Thoda complex lag raha hai, agar yaad kare toh hum khud se algorithm kaise banayenge Pls reply...

[@maccall0108]

please cover the topic 2D array Dynamically

[@aakashthakre244]

Ha yaar

[@gaishiya7696]

instead of allocating count array size as 10,we can use k+1 right ? actually that's why we are finding the max element .

[@deveshdubey6776]

Why mam said we can't dynamically allocate memory to count array?

[@SaurabhKumar-ft3gt]

same question..

[@devjoshi7062]

idk why she did but looking for restricted memory prespective, you will surely get runtime error as it will reach past the maximum time allowed. Idk but still try, it can work also

[@mitadey3876]

Can we skip the cumulative sum part and based on the index of count array add index of count array in original array.

[@vrajeshmodi4928]

There is one minor mistake in notes program ,You have to take 'k+1' as count array size. (Problem is in Line 6). Overall best course at KZbin for DSA loved it.

[@faizanullah6922]

thanks dude 🙂

[@aaryan__bondekar9778]

yes, i had same doubt!

[@nakulgite7565]

Do we need to learn data-structure and Algorithm first to complete this course.. pls reply🙏

[@sourabhchoudhary7289]

This course will teach you DSA .

[@maulikshah28]

This course is of DSA, you don't need to learn anything before this

[@piyushverma8207]

How did she do that. She printed the array in main function. But for all we know that she only sent the values of arr in the function without referencing it.

[@aakashthakre244]

She stored the value in original array in function in last lines

[@piyushverma8207]

@@aakashthakre244 You got that wrong. She could access the array from a function because arr is a pointer. If you try to do the same thing with an int variable, you will not be able to do that

[@shivanshpratap3624]

@@piyushverma8207 GCC Compilers takes array in functions as a reference by default

[@akashayanand]

why is there overhead of creating a 'position array' our goal can be achieved from the count array itself. this code is not optimal?

[@nishantgarg2815]

can't you simply use count array to put numbers in new array since you know frequency of each number.Something like int k=0; for(int i=0;i0){ for(int j=0;j

[@lasbutious116]

I have the same exact question. will it not be a lot easier to create the new array because we already know the frequency of each element?

[@iamkanishkyadav]

Because then Time complexity will become Big-O of N^2 ie O(n^2) . But we want optimal O(n).

[@nishantgarg2815]

@@iamkanishkyadav Its O(N) not O(N^2).Check again

[@iamkanishkyadav]

@@nishantgarg2815 I am stuck, right now, but ur code is not simple O(n), may be something else. May be I need to go more depth in time complexity.

[@lasbutious116]

what if the range of data is big? suppose array=[100000,1,80] then except for these 3 values all 100000 variables will have count 0 but still we have to traverse through all of them

[@deepakmodi9343]

Nice explanation and a nice video.

[@harshwasnik7636]

Di will it work for negative values? Coz u can't store no. of times that element occurred. Please do correct me if I am wrong.

[@thesomebody5439]

I guess we just have to mod the values

[@hunterzolomon6842]

@@thesomebody5439 ni be lolu

[@deveshdubey6776]

counting sort is incapable of sorting negative numbers...but there is a modified counting sort which can do it

[@abhijeetgautam587]

Find the minimum element of the array. Then declare an integer: int convert_factor = (0 - minElement); Now add convert_factor to every element of the original array. Then use the usual QuickSort algorithm and obtain the sorted array. Finally, before printing the sorted array, subtract convert_factor from each element of the sorted array.

[@leo-x1d1f]

in notes please correct count array size is max+1 that means k+1 but in note take only k which is wrong

[@shubhamkale735]

When yoou are at another level of coding ......... Thank you aman sir and team ... l

[@adityamishra8296]

maine same code likha tha not working😥😥

[@NitishYadav-rb9ki]

Web development ka course kab aayega

[@fardinalam7290]

how could be time complexity is O(N)??? when she used first loop as a traverse whole array after that used 2,3 loops?

[@sumitkevlani5740]

Hamne maximum Element nikalkar ke us length +1 ki array bnayi but suppose agar array me negative number aaya tab to yeh algorithm kaam nhi aayega

[@gauravjha4209]

Bro plz help me how to improve Maths my maths subject is week but i hope u make a one video for us

[@ashwinshetgaonkar6329]

we can allocate memory for dynamically for array,

[@abhisheknishad2401]

Awsm mam

[@makarandpundlik1083]

Can we sort -ve elements using this method ?

[@AkshitPanday]

No this can be applied only on array with non-negative elements as frequencies cannot take -ve indexes

[@abhijeetgautam587]

Find the minimum element of the array. Then declare an integer: int convert_factor = (0 - minElement); Now add convert_factor to every element of the original array. Then use the usual QuickSort algorithm and obtain the sorted array. Finally, before printing the sorted array, subtract convert_factor from each element of the sorted array.

[@makarandpundlik1083]

@@abhijeetgautam587 great, that will work.

[@jiosim1377]

Isnt the time complexity of count sort O(n+k)?? Can someone explain please??

[@sawanpatel3491]

it's O(n)+O(k); but we are performing on large number of elements i.e. 10^7. so we ignore it.

[@vinaywalia8723]

there so many for loops so that can increase the time complixicity just asking

[@sourabhchoudhary7289]

Actually O(n)+O(n) is approximately equal to O(n)!

[@rambabupatidar3092]

how No of element in count array are coming from max element of arr array . For eg . If arr is 6,8,12,3,4,5,2,6 In this case k will come out to be 12 but acutually k must be 7 as there are only 7 distinct element in array.

[@walwinvirlar6873]

I did not understand when she said we can't make dynamic array then 5 lines later makes a dynamic array of size n could someone explain to me how?

[@aakashthakre244]

Same ques

[@harendraseervi5525]

#include using namespace std; int main() { vectorv; int arr[]={1,5,3,1,2,3,4,4,2}; int maxno=-55; for(int i=0;i

[@minimaxhindi]

Please create a video on bucket sort

[@aaryansaha9616]

Can someone clear it ? How does count[ arr [ i] ] ++ ; work ?

[@snehilsinha4689]

basically, you are using the technique here called hashing in which you are making a new array to store the count of every element of the original array. This works in the following way -> 1. You are using the index number of the new array to represent the value of your array element i.e. arr[i] 2. Then you are incrementing on that index each time your element occurs in the array by doing count[j]++ where j=arr[i] works as the index. 3. Thus in this way the new array stores the count of each element of the array and its index helps identify the corresponding elements which will be useful while accessing it. Hope it helps 🙏

[@monikaraut5266]

Here count is basically Array of counts, in which you are storing count of elements, you will store count of 0 at index 0, count of 1 at index 1 , count of 2 at index 2 and so on.. e.g. When you see 2, you will increment value at index 2 in count array

[@nageshwarmitkar2708]

Bhaiya please suggest best videos for digital marketing.

[@pritishpattnaik4674]

can we do this by combination of vectors and pairs ?

[@shubhamhelloworld321]

Yessssss

[@aakashthakre244]

Many doubts no solution on net also please tell us where to ask doubt so teachers can reply

[@gandhijainamgunvantkumar6783]

Amazing explanation :)

[@sahilbheke4083]

6:56 why can't we take k as a size

[@aaruljuneja4875]

Please🙏🙏🙏🙏 also make video on python language

[@anuragpandey3341]

FAANG Motivation video: 1day - 1million views Actual knowledge to crack FAANG companies: 1year - 50k views What's the use of motivation without hardwork?

[@ishangupta9294]

totally agreed! everybody wants to work in FAANG but dont want to work upon what it takes to get there

[@faizanahmed9304]

What for negative numbers?

[@gauravdhiran9474]

Code is not printing any output , can you please give me the solution what can I do to get the output

[@rudrakalyan4567]

Thank you mam

[@saswatsamal1199]

why can the array be dynamically allocated at - 6:57

[@sahilgupta7170]

make array of size k+1 it will work

[@bestluckstar2967]

How can we apply the counting sort algorithm to sort array with negative numbers?

[@shailendramaheshwari5471]

by taking the abs() value of the negative elements in an array

[@saisriangajala8399]

Why do we iterate from back why can't from front??

[@depressinglyfunny]

i have a doubt? why cant we make a dynamic array in the count sort function??

[@siddharth4069]

Counting sort only works when the range of potential items in the input is known ahead of time. If the range of potential values is big, then counting sort requires a lot of space

[@avinashgupta2308]

int count[K+1] --> why not this ? but count[10] this ?

[@vijaysbuddhi5252]

Guys how much time did it took for U complete this lec? Just asking

[@aritraganguly3957]

does count sort come in interview

[@aakanshasoy3921]

Last element me Garbage value show hora hai use kese solve kru ?

[@sit33darshanpagar16]

3:51 why we are decrementing and then storing value in array. 😔

[@its_neel_ok]

cause we added the values to get the position. So, if we want the position in sorted order we have to go reverse(from end to start), we can' t do that from start to end

[@md.ualiurrahmanrahat2400]

there is a problem with the code. when the original array size is less than the max element of the array, then the program crashes. For, ex;: arr[] = {18,1,8,1,20} here n = 5, but k = 20; so, array can't take elements if you can't handle correctly the size of the array inside the function. Wish much focus was given in the concept explanation than animation of the video

[@shivanshpratap3624]

Why so?

[@Abhishek-zx5zz]

Negative elements ma frequency kesa count kar payga

[@satyamsingh3]

Bouncer bhai sahab

[@angadchoudhary2773]

Can anyone explain the word at 6:57 ?

[@pratham9954]

Why he is providing course for free even there are no ads in all course??

[@AdityaKumar-pp4xw]

He has multiple channels too, Long term investment I guess

[@mohammadanas7929]

Thku mam❤️❤️

[@sachinkashi]

What if there are negative numbers also included to be sorted

[@mbasimirfan5465]

ye hi to masla aa raha

[@Yahy_Sani]

#include using namespace std; int main() { int n; cin >> n; int a[n]; int N = 0; for (int i = 0; i < n; i++) { cin >> a[i]; N = N < a[i] ? a[i] : N; } int countArr[N + 1] = {0}; for (int i = 0; i < n; i++) { countArr[a[i]]++; } int k=0; for (int i = 0; i < N+1; i++) { for (int j = countArr[i]; 0

[@ayushmishra1396]

What if the value of element of array is -1

[@rohanupahyay3791]

Notes??

[@shreyasingh4680]

what if the array contains negative elements?

[@higgsboson3882]

then you would have to find the minmum element and make array accordingly for eg -3 -1 1 3 4 5 so count array will have 0 1 2 3 4 5 6 7 8 where 0 stores occurences of -3 , 2 stores occurences of -1 ... so on

[@vashishthgajjar1968]

wait what kind of sorting method is this?

[@ServingTech]

In Your Coount_Sort Program You Cannot Sort The Negative Values.

[@yashgandhi9698]

can be done using origin shifting if a mixture of both +ve and -ve just reverse the sign in case of all negative...

[@ServingTech]

@@yashgandhi9698 #include using namespace std; void Count_Sort(int arr[],int n, int Min,int Max,int ans[]) { int range=Max-Min+1; int farr[range]={0}; for(int i=0;i n; cout > arr[i]; Max = max(arr[i], Max); Min = min(arr[i], Min); } int ans[n]; Count_Sort(arr,n,Min,Max,ans); for(int i=0;i

[@ServingTech]

Like This ?

[@csiddharth380]

Bhaiya G plz is video k bhi notes upload krdo

[@sakshithakur8465]

Please upload notes 🙏🏻🙏🏻🙏🏻

[@pranshuprapranshu304]

you didnt told why you started , loop from i=1 and not from i=0 (~_~)

[@TRICK_OF_THE_DAY]

Why you don t have Persian subtitle?

[@shravakjain5163]

how can we think so far like that..? i am unable to solve new question

[@jiosim1377]

Bro all these sorting algorithms are standard algorithms u cant think on spot nd get the logic. U have to learn and remember the logic

[@aadil4236]

What happens if there are negatives?

[@Ayush_.]

fir to map leke hi solve krna padega🤓