Counting Sort: An Exploration of Sorting Special Input In Linear Time
ฝัง
- เผยแพร่เมื่อ 29 มิ.ย. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement counting sort. Analyze its best, average, and worst case time complexities.
This algorithm generalizes to anything that you can map to a positive integer value for sorting (like sorting an array of characters).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - วิทยาศาสตร์และเทคโนโลยี
Table of Contents:
Introducing Counting Sort 0:00 - 2:08
Walking Through The Algorithm 2:08 - 3:18
Step 1: Initialize Occurrence Array 3:18 - 3:27
Step 2: Count Occurrence In The Original Array 3:27 - 4:34
Step 3: Aggregation of Occurrences 4:34 - 6:28
Why Did We Just Do That? 6:28 - 7:54
Step 4: Placements 7:54 - 10:14
Sorting Finished. 10:14 - 11:52
Analyzing Counting Sort 11:52 - 15:43
We Get The Final Bound 15:43 - 16:10
Wrap Up 16:10 - 17:08
The code for the problem is in the description. Fully commented for teaching purposes.
Back To Back SWE
Hi ,
I have seen many of your videos those are really good . In this one , I would like to understand why we need to do summation .
I have tried to come up below solution without doing summation it passed all the testcases on leetcode . Am I missing something
class Solution {
public List sortArray(int[] nums) {
if(nums == null || nums.length == 0){
return null;
}
return countingSort(nums);
}
private List countingSort(int[] nums) {
Integer maxNum = null;
Integer minNum = null;
int [] countingSortPositive = null;
int [] countingSortNegative = null ;
for (int index = 0; index < nums.length; index++) {
int value = nums[index];
if(value >=0){
if(maxNum == null){
maxNum = value;
}else{
maxNum = Math.max(maxNum, value);
}
}else {
if(minNum == null){
minNum = value;
}else{
minNum = Math.min(minNum, value);
}
}
}
if(minNum != null){
countingSortNegative = new int[Math.abs(minNum) + 1];
}
if(maxNum != null){
countingSortPositive = new int[maxNum + 1];
}
for (int i = 0; i < nums.length; i++) {
int value = nums[i];
if(value >=0){
countingSortPositive[value]+= 1;
}else {
countingSortNegative[Math.abs(value)]+=1;
}
}
List list = new ArrayList();
if(countingSortNegative != null && countingSortNegative.length > 0){
for (int i = countingSortNegative.length -1 ; i >=0; i--) {
if(countingSortNegative[i] != 0){
for (int j = 0; j < countingSortNegative[i]; j++) {
list.add(-i);
}
}
}
}
if(countingSortPositive != null && countingSortPositive.length > 0){
for (int i = 0; i < countingSortPositive.length; i++) {
if(countingSortPositive[i] != 0){
for (int j = 0; j < countingSortPositive[i]; j++) {
list.add(i);
}
}
}
}
return list;
}
}
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
Sorry to be so offtopic but does anybody know a trick to get back into an instagram account?
I somehow lost the login password. I would love any tips you can give me.
Landed a job last month and relied on your videos a lot. Just donated some money to your Patreon. Thanks for everything!
Aw, thanks
Nice explanation. You could've picked other example - the one that contains duplicated elements. It would make it easier to understand why the running sum array is needed.
The running sum step is not necessary, it is only one version of counting sort (the more commonly seen one which is why I covered it). You could just create an occurrence array and from there go straight to placement. The asymptotic complexity is still the same.
Why would duplicated elements necessitate the aggregation step?
@@BackToBackSWE you're right, it's possible to do it without performing a sumation if we're sorting just numbers like in your video. Although I still think it makes it easier to understand if you have duplicates in the array, see this visualization: th-cam.com/video/7zuGmKfUt7s/w-d-xo.html
Yes, that's the version we covered ... I'm still confused on how duplicates change anything. We would always be sorting positive integers (whether we codify actual objects/any other non-integer value we want to sort into an integer mapping). Can you clarify, I must be missing something
@@BackToBackSWE ok maybe it was just me but after watching your video I wasn't completely sure why running sum step was needed. But if you perform this algorithm on an array with duplicates, you see that running sum array is actually useful, it helps to place a correct amount of a given element in the final array. Sorry for not being clear enough before :)
As for the difference between sorting just integers vs some other structures, see this post because it explains it a lot better than I could (it also touches the topic of cumulative sum): stackoverflow.com/a/32235015
@@mzmzgreen Ahhhhhh, gotcha. That link cleared it all up. Yes, you are right, that is why the aggregation sum step is needed (in the case we are not sorting just raw numbers) - so we can go to the original array and place objects in the right index (and at that point the 'count' array will be a literal "guide" for us to know where to put what based on its key integer value).
Dang, I learned something, thanks
Is it just me or is this algorithm just confusing in general? I reckon you did a good job explaining it as a simply as possible! No matter what resource I look at this algorithm just does not make sense to me hahah.
Nah, I dun goofed
You explain in a very smooth manner. Your videos are so soothing to watch. you are so calm
Thanks so much for your videos to help me understand BFS and DFS, now you are my go to channel when I learn new algorithms
I've seen many implementations but only this one matches with my uni's and is fairly understandable. ^^ Thank you, keep up the good work !
nice
it does not work for duplicate numbers i think.. Since there are no negative indices any way pls tell me how to implement this for negative numbers as well.
@@shreevatsalamborghin int max = Arrays.stream(a).max().getAsInt();
int min = Arrays.stream(a).min().getAsInt();
int range = max-min+1;
int [] count = new int[range];
int [] output= new int[a.length];
//store count of each character
for(int i=0;i
Very underrated educational content. I just subscribed and hope to learn more programming concepts. Keep it up
thx
Can't believe it took me so long to find you. Your videos are the best.!!
I love your videos! I'm taking algorithm design course and you explain things better than my prof lol
We can actually modify the counting sort to even include -ve integers as well. For that we can use extra space in the same array with one partition for +ve integers and one for -ve. and when we finally count the numbers we start from the 2nd partition (which has negative integers stored only their +ve magnitude which will be converted to -ve when producing output from the partition 2) and then after completing it we use the first partition for +ve integers.
yes, thank you
You know what? You're so good at teaching. Let keep the good work and your effort will definitely paid off sooner or later.
Appreciate that!
You have a talent in teaching. I was so confused by watching other videos, your video was the easiest to understand.
Happy to hear that!
Cant wait for you to hit 100k subscribers. You'll get it done in no time props to you man
hey
Back To Back SWE hey
I don't skip your videos that's how I can help you and I suggest other to do this .... Thanks bro ... You are one of the best computer teacher
sure
Thank you sir you replied it's a great pleasure to me
great video. been stuck on this for a long time
Great to hear!
Thankss a lot for this explanation really clicked for me!
I think the terminology of prefix sums is used widely, i was confused with running sums, but in the end I got it that it was actually prefix sums that I learned for other algorithm before.
By the way prefix sums ONLY NEEDED WHEN WE HAVE DUPLICATE VALUES IN THE ORIGINAL ARRAY to avoid extra nested loop while reconstruction your sorted arrays.
And you forgot to mention why we started reconstruction the sorted array by traversing from the end of the array. The reason is to preserve the STABILITY of the array. You can start from the beginning, in that case the stability of the array is not preserverd
nice
i gotta say this video is awesome i've seen a few videos and non of theme were this awesome
thx
Great explanation Ben! One can easily follow :). do you have radix sort explanation video created? if not, can you please create one for Radix sort ?
Thanks and I almost made one but go too busy during the semester, yeah i can
@@BackToBackSWE nice. Looking forward to it! thanks Ben for all great videos. One thing that would be great to include in that video would be when should you use Counting sort vs Radix sort? I figured when you have input like [ 0, 11111111111111111] counting sort would perform slow vs it would be very easy for radix sort.
The example you use is too special and not general
Yeah, my bad. Code in description to clarify but yeah, my fault for that, I got lazy.
great explanation. easy to understand.
Hi! I love your videos! Where exactly is the code you reference to be in the description? Is it in the website that is linked?
You can check out the code repository on backtobackswe.com/
in CLRS it says that K represents the range of the input from (O, K) not how many unique elements there are
ok
brilliant explanation, thank you
This video is amazing ,good explanation.
sure
I love your videos! Great explanation
Thank you!
We go from back to make sure that the sorted array is stable. We are basically placing the last occurence of the element in the last possible index it can be placed at.
Subbed. Thank you boss. Ur gono b a star
sure
Given k - unique values and n - all values, we could conclude that k
Great explanation!
thanks
i guess its important to emphasize that the mechanism is at is, because an element can also have multiple occurrences in the initial array.. then its important to have the intermediate running sum, starting from the back.. because the order needs to be maintained (FIFO), even if the numbers are the same
This is a very good video. However, if the example is an array with duplicates, it would be better. Thanks
yes
Great explanation, but I with you'd use different test set as an example, it does not show how algorithm behaves in case of duplicates.
yes
Has the code been removed?
The repository is deprecated - we only maintain backtobackswe.com now.
Hi there! I've just found this video and its helping me a lot! But I have a doubt. If I don't know the size k of my count array is it still worth to use counting sort? I have an 10^6 numbers in my vector but I don't know their sizes.
im not sure, I forgot counting sort since I shot this, I need a refresher
Counting sort is most effective when
1) You know the range your values will be in
2) You're comfortable with the space implications of building a count array of the size of the range. (Space tradeoff)
In this case it seems you're not sure what range your values may be in. Moreover, even if you were, 10^6 values would mean a lot of space and time to build a count array (Assuming little to no duplicate values i.e all 10^6 are fairly unique.)
@@bolu3307 thanks
Why do you start from the last item in the array instead of the first item for the final loop?
Can you explain why we iterate backwards while doing placements in the original array?
It is just the more common implementation, you can go the other way too
@@BackToBackSWE It also makes the implementation of a sorting algorithm stable if you iterate backwards
Thank you!
ye
Great video! but I don't seem to find the code? Where is it?
Repository is deprecated and no longer maintained
I think you should have explained the algorithm further by showing why exactly (after performing the accumulative 'running sum') does each index denote the last possible occurrence of value (i). Great video nonetheless, thank you!
yeah, you're right
what about duplicate value in the array? I cannot figure it out with this algorithm.
8:02, why do we move backwards in the array arr? Is there any reason behind this? Why not moving forwards?
Is there any particular reason as to why we are trying to find positions for our numbers in the given array from the last? We can do a normal traversal of the given array right? I'm talking about the last placement and decrement of count step.
yeah we can
Actually found out the reason:
1. When we use counting sort as a subroutine in radix sort, we need to maintain the relative ordering, there we must traverse from the back otherwise, radix sort fails.
That's the reason! Love your videos man. Thanks.
@@arunm619 nice
Your explanation is pretty good, but the example you use is too simple which occurs some confusion. Thank you anyways.
yeah
Good video and thanks for that. But wish you had used a better example. Array of size 5, indices 0-4, array values 0-4. Simply too confusing and required several iterations to get it.
yeah I know - I have a memory of every video I didn't make all I wished it could be. This is one of them
Wow tHANKs!
sure!
Dont we need two for loops(i mean nested) to get the occerences?
I don't remember the code for this to be honest
I got it , I got it , I got it , I got it , Thanks 🔥
You should have a zero and well other numbers that aren't 1 in your c array.
Any idea on how to write code to sort in
descending order (exam tomorrow)?
how was the exam - got to this late
I don't think I passed. I guess they thought we would all cheat and made it extra hard.
I figured it out in case this could help someone:
To order in non increasing manner:
For i=k-1 down to 0 {
C[i] = C[i] + C[i+1]
}
K being the length of the C array.
I am now at 3:56 . Everything still clear . Thanks
I am at 7:32 , and still understand everything
ok
ok
Thank you.
sure
"At the end of this, we are going to generalize this to mapping anything to an integer."
Where is this done?
I think I forgot, ya got me. But yeah, it is as stated, if we can map an object to an integer (or establish that relationship in any way) then we can sort the data based on those integer mappings. I just forgot to do an example of it but it is the same thing.
Your videos are awesome, great explanation. I Have a few questions not related to this video but for interview preparation.
I already did about 70 leet code but after a month when I look at the same problem I solved it I don't remember which algorithm I used and it takes me 30 mins or one hour to solve it again. Is this normal? Can you please guide me in these 3 questions:
1. When were you looking at the correct solution -- before you began the problem when you got stuck, only after struggling to solve it yourself? How long until you would look at the solution, typically?
2. What would you do after you'd not solved the problem, but looked at the answer?
3. What would you do after you did solve a problem?
yes that's normal - the amount of leetcode you do has a very loose correlation to preparedness. It's not about problem count - it's about topic comprehension.
1.) It depends, when studying you may just fundamentally not have the toolset to solve a problem, so trying can waste your time if even the brute force is locked from you. A problem like this is kind of bad since it doesn't demonstrate critical thinking...but you can often recognize it. If you know you can brute force you do that and then maybe give it 10-20 min beore you give up? really up to judgement.
2.) I'd want to deeply understand the solution, why it works, and the principles it has taught me to apply elsewhere. Some problems are good for this and some are less useful.
3.) I'd check the solutions to see if there was a more optimal way.
Hi, amazing video, but I have one question:
for this init array => [ 0, 200, 5000] => k would be 3 or 5001?
I don't remember to be honest, I'd have to recap on counting sort
I think it's 3, from how I understood it
k would represent the range of nos so max - min +1 = 5001
5001 , here counting sort is not efficient
Why do you need to traverse backwards for placement?
any plans for tackling 621. Task Scheduler in leetcode?
Not sure when I'll do that, I'm just winging it right now
dude i fucjiubng love you
thanks
TYSM
ye
I'm confused on why we say n+k instead of n, because we know for sure k will be smaller or equal to n (worst case equal to n), in that case, shouldn't we ignore it?
Correct, I think it is a matter of specificity because they are different parameters.
Asymptotic bounds do ignore constants (by their very definition of picking an arbitrary c to multiply by f(n) to bound T(n)), but even if n upper bounds k, it is still not a constant. It should be considered in the asymptotic notation since it is another parameter that an external caller can modulate.
The end behavior is linear through and through, hence "linear time".
@@BackToBackSWE Thanks a lot for the detailed reply!
bro I cannot find selection sort on your channel? i remember you had it
I think it is somewhere
Back To Back SWE 😂. Oh okay I see how it is naowwwww 😂
15:45
the symbol looks like Baymax from Big Hero 6 lmao
ok
Can you do a video on Radix Sort please?
sure
homie can u drop new videos on Rod cutting dynamic programming etc.
I don't want to
Back To Back SWE not fair dawg
But what if we do not get k
final array index can start from0/1
nice
Confusing, should use letters instead, don't know if you are referring to the number or the index. Didn't even show duplicate case.
yeah u rite
hero
Your explanation of K is wrong. K is not the number of unique values in the input array. If it were so, for example, for an input array [1,0,2,999], your count array would be [0,0,0,0] i.e have index 0 to 3. This will not work as the program will not be able to access count[999] and increment occurrences. K is the max value in the input array. So the count array should, in this case, be of size -999- 1000
edit: size = k+1 = 1000
Did I say that? Don't remember, if so thanks for the catch.
@@BackToBackSWE np. between 2:21-2:26.
2 arrays and cumulative summing for sorting simple integers is a bit of an overkill. it's good for keeping the sorting stable, but stability is meaningless when sorting integers. besides, since the elements are unique, counting is unnecessary, so the example is probably not the best (woulda been great for radix sort).
ok
ZERO is a non negative integer not a positive integer. The upper bound for the second and forth summation should be n not n-1.
You are not a professor my friend, when you don't know something correctly, don't make such video clips and waste our time.
Please stop teaching, teaching is an art, and it is just your assumption that you can teach. + even if you want to do it, prepare on paper first and then record. Thank you