Table of Contents: (this is a long one, grab some popcorn) We Will Do Something Different 0:00 - 0:17 Self Promotion 0:17 - 0:33 The 2 Fundamental Operations of Comparison Sorting Algorithms 0:33 - 0:46 Introducing How Bubble Sort Works 0:46 - 2:18 We Begin To Bubble An Item Up 2:18 - 3:21 We Continue Comparisons 3:21 - 4:27 1st Outer Loop Pass Is Done, 2nd Outer Loop Pass Now 4:27 - 5:01 Our Mission Today 5:01 - 5:45 The Best, Average, and Worst Cases For Input To Bubble Sort 5:45 - 6:05 The Best Case 6:05 - 6:56 The Worst Case 6:56 - 7:40 The Average Case 7:40 - 8:06 Summation Notation 8:06 - 9:30 Gauss Formula 9:30 - 10:27 Worst Case Analysis 10:27 - 11:59 We Got Kicked Out... 11:59 - 12:06 Worst Case Analysis (continued) 12:06 - 13:16 Our Task Is Now To Simplify 13:16 - 13:49 What Does The Inner For Loop really Say? 13:49 - 15:32 Simplifying The Inner For Loop 15:32 - 16:11 Our Last Task: Simplifying The Outer For Loop 16:11 - 19:02 We Use Gauss' Trick To Simplify The Outer For Loop 19:02 - 19:20 The Final Value For Worst Case Swaps In Terms of N 19:20 - 19:57 Geekin' 19:57 - 20:07 For The Worst Case, # of Comparisons = # of Swaps 20:07 - 20:36 A Bus Interrupts Me 20:36 - 20:40 The Best Case Does No Swaps 21:00 - 21:34 Expected Value Definition (So We Can Analyze The Average Case) 21:34 - 23:43 Let's Calculate The Swaps For The Average Case Now 23:43 - 26:10 Final Answer For The Average Case 26:10 - 27:42 Subscribe 27:42 - 28:26 The code for bubble sort is in the description. This took forever to make.
Ive watched so many interview review channels and youre the easily one of the best out there. I hope the channel gets more traction. Just pure easy to understand analysis that struggling learners need. Youre a god sent. Thank you.
OMG this is so helpful thank you so much for making this video! I have an exam tomorrow and this is the best study material I've found. Thank you for putting in the effort!!
Wow, thank you. I'm literally half way through my semester in data structures and I finally feel like I can see the connection between the concept and the code. I was totally stuck. Your explanations are awesome!
Hey. Im having some understand issues with 19:37. Why to we change n to n-1 in Gauss Formula? Is it because of the i-1 or because we start with i = 2 instead of i = 1? And doesnt the i = 2 for i -1 negate itself so we start to count from 1 to n? Feels like in that case we could use Gauss Formula as it is. Best regards
At 20:51 the formula for runtime is n(n-1)/2 where in best case scenario n will be 0 as there will be no swapping leading to best-case runtime to O(1) which is not correct best-case complexity for the bubble sort. Bubble sort best-case runtime is achieved by modifying the algorithm to have a flag to break the outer loop if the array is already sorted leading to have the best case O(n). Otherwise with the solution you mentioned even the best-case scenario will give runtime of O(n2).
Appreciate the effort.Kindly, make sure that the viewer can see the pseudo code while manually implementing the algorithm, so that we can compare it with implementation
many many thanks to you bro,for your hard working to creaate this type of excellent tutorial.it is my request to you for creating merge sort algorithm .
Hey bro, this was a really nice video and I understood most of it, I didn't quite follow the pseudocode though. I wasn't sure why you started as i=2 for the summation. Other than that it clarified my doubts on how bubble sort works
That is a really good question. I'm honestly not sure. EV is attained by multiplying each possible outcome's value by the likelihood the outcome will happen. Then taking the sum across the values. When the outcome is a qualitative measure that scrambles my brain. Here are some things I pulled up from researching this: Random Variables Aren't Always Numbers: www.quora.com/Does-a-random-variable-always-take-on-values-that-are-numbers Assigning Values To Qualitative Outcomes: math.stackexchange.com/questions/1700381/expected-value-of-a-coin-toss Doesn't do much but, ah well, I'll figure this out someday.
You're the fucking man, I have a algorithms exam on tuesday and this video helped a lot, someone already said it but if you could do analysis of merge, heap, and insertion sort thatd be amazing
I just saw, thank you bro for the knowledge, you're a lifesaver! P.S: I see you do vids at UMD, I'm actually a student there, I'm using your videos to study for my 351 exam haha
@@mohammedarafat8059 hahahaha, hey, can you do me a favor and share the heap sort video in piazza? It'd be weird if I did it. Or not...I don't really care but I think it'd help many people.
@@BackToBackSWE I'm not on the piazza for this class, never signed up lol, but I sent your vids to a few ppl, one who knows you too btw, who are taking it. You should post the bubble and insertion sort vids on there tho bc those were really helpful for the practice exam. It's not weird if you're promoting a service you provide if its useful to the people you're promoting it to. Self promo is only weird if you're promoting a service in a setting where no one wants to hear it, and trust me the ppl in my class need your vids lol
why dont you before starting always remind people that the position of n is the index and it starts at 0 always, so we do i+1? i feel like a constant reminder would help. or maybe everyone knows this and I'm new so I need this but everyone else already ahead of me :D
Table of Contents: (this is a long one, grab some popcorn)
We Will Do Something Different 0:00 - 0:17
Self Promotion 0:17 - 0:33
The 2 Fundamental Operations of Comparison Sorting Algorithms 0:33 - 0:46
Introducing How Bubble Sort Works 0:46 - 2:18
We Begin To Bubble An Item Up 2:18 - 3:21
We Continue Comparisons 3:21 - 4:27
1st Outer Loop Pass Is Done, 2nd Outer Loop Pass Now 4:27 - 5:01
Our Mission Today 5:01 - 5:45
The Best, Average, and Worst Cases For Input To Bubble Sort 5:45 - 6:05
The Best Case 6:05 - 6:56
The Worst Case 6:56 - 7:40
The Average Case 7:40 - 8:06
Summation Notation 8:06 - 9:30
Gauss Formula 9:30 - 10:27
Worst Case Analysis 10:27 - 11:59
We Got Kicked Out... 11:59 - 12:06
Worst Case Analysis (continued) 12:06 - 13:16
Our Task Is Now To Simplify 13:16 - 13:49
What Does The Inner For Loop really Say? 13:49 - 15:32
Simplifying The Inner For Loop 15:32 - 16:11
Our Last Task: Simplifying The Outer For Loop 16:11 - 19:02
We Use Gauss' Trick To Simplify The Outer For Loop 19:02 - 19:20
The Final Value For Worst Case Swaps In Terms of N 19:20 - 19:57
Geekin' 19:57 - 20:07
For The Worst Case, # of Comparisons = # of Swaps 20:07 - 20:36
A Bus Interrupts Me 20:36 - 20:40
The Best Case Does No Swaps 21:00 - 21:34
Expected Value Definition (So We Can Analyze The Average Case) 21:34 - 23:43
Let's Calculate The Swaps For The Average Case Now 23:43 - 26:10
Final Answer For The Average Case 26:10 - 27:42
Subscribe 27:42 - 28:26
The code for bubble sort is in the description. This took forever to make.
I have no doubt this will be one of largest channels out there for SE interview prep. keep going bro!
haha thanks
I hope not small niche channels are the best
@@spectermakoto9029 wut
Ive watched so many interview review channels and youre the easily one of the best out there. I hope the channel gets more traction. Just pure easy to understand analysis that struggling learners need. Youre a god sent. Thank you.
sure
OMG this is so helpful thank you so much for making this video! I have an exam tomorrow and this is the best study material I've found. Thank you for putting in the effort!!
sure, I think I'm in your class haha
This is definitely one (maybe the one) of the best channel!
thx
Wow, thank you. I'm literally half way through my semester in data structures and I finally feel like I can see the connection between the concept and the code. I was totally stuck. Your explanations are awesome!
Everything about this video is perfect. Thank you.
nice, u perfect
Hey. Im having some understand issues with 19:37. Why to we change n to n-1 in Gauss Formula? Is it because of the i-1 or because we start with i = 2 instead of i = 1? And doesnt the i = 2 for i -1 negate itself so we start to count from 1 to n? Feels like in that case we could use Gauss Formula as it is. Best regards
I don't remember the math much in this video
Gauss formula will not work the way you are expecting. n is relaced with n-1 because of the lower bound 2. The precise answer would be (n(n-1) /2 ) -1
You’re gonna get really big soon!
haha, maybe...maybe not. I'm content doing what I'm doing.
The most helpful video ever! Thank you for taking the time to do this.
Please make videos on merge , quick sort and counting sort..
k
Very ,very thorough explanation. Excellent.
It's the best explanation. Thank you for sharing.
I chuckled when you said you weren't sure what Gauss' last name was. Nice video. Your content is awesome.
So what will be the best case time complexity? Is it O(n^2) according to your algorithm?
Yes. O(n) is the best case for (modified) bubble sort if the array is already sorted, there is another video for that
thank you so much.....this video helps me to understand the topic clearly.
great
Brilliance at its best. Good job man. Thumbs up as i understood the topic really well from your video
Greetings from Turkey, thank you for your nice explanation.
This really helps me a lot. Thanks!
great
Thank you many times. You've been helping me a lot.
Thank you, we have got your back!! 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Awesome explanation!!!
At 20:51 the formula for runtime is n(n-1)/2 where in best case scenario n will be 0 as there will be no swapping leading to best-case runtime to O(1) which is not correct best-case complexity for the bubble sort. Bubble sort best-case runtime is achieved by modifying the algorithm to have a flag to break the outer loop if the array is already sorted leading to have the best case O(n). Otherwise with the solution you mentioned even the best-case scenario will give runtime of O(n2).
This is too long to read (im fast replying to comments) but i love you
in my opinion you are better than mit.Thankyou for depth
Thank you Surendra 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
just found a great channel for algo and data struc
You have become my fav teacher :)
so much explanation.
keep it up bro
thanks
Appreciate the effort.Kindly, make sure that the viewer can see the pseudo code while manually implementing the algorithm, so that we can compare it with implementation
k
I wish you and your channel the very best bro! 🙏🏽✨☝🏽🎊
I rarely write comments. But this video is very useful. Thank you so much for all the efforts and keep doing great content.
Thank you, means a lot 🎉 You can also check out our free DSA course - backtobackswe.com/
Keep the good work going on brother...
many many thanks to you bro,for your hard working to creaate this type of excellent tutorial.it is my request to you for creating merge sort algorithm .
I already did
very nice explaining ! thank u
sure
this is just amazing , thank you
Great video as always
thx
Really love ur videos! best till now for me. Also, what is the name of the music at the end?
Hey bro, this was a really nice video and I understood most of it, I didn't quite follow the pseudocode though. I wasn't sure why you started as i=2 for the summation. Other than that it clarified my doubts on how bubble sort works
How would you find the sum of possibilities if we had 6 different color on dice instead of 6 different numbers?
That is a really good question. I'm honestly not sure.
EV is attained by multiplying each possible outcome's value by the likelihood the outcome will happen. Then taking the sum across the values.
When the outcome is a qualitative measure that scrambles my brain. Here are some things I pulled up from researching this:
Random Variables Aren't Always Numbers: www.quora.com/Does-a-random-variable-always-take-on-values-that-are-numbers
Assigning Values To Qualitative Outcomes: math.stackexchange.com/questions/1700381/expected-value-of-a-coin-toss
Doesn't do much but, ah well, I'll figure this out someday.
This video is very useful, thank you so much.
Can you make a video on loop invariant ant
شكرا علي الشرح الوافي والممتع تحياتي من ليبيا
Wikipedia says n# swaps for average is O(n) .. not O(n^2) why?
Can u link - not sure what you are referencing
@@BackToBackSWE sorry it was n# comparisons
God bless you! You saved me!
ye
Another great video. What do you think about competitive programming?
Haven't tried it, but it is very similar to what we basically get asked in SWE interviews. Good book on it (only skimmed this): cses.fi/book/
Vry gud performance I likes it
thx
You're the fucking man, I have a algorithms exam on tuesday and this video helped a lot, someone already said it but if you could do analysis of merge, heap, and insertion sort thatd be amazing
I have done all of those.
I just saw, thank you bro for the knowledge, you're a lifesaver!
P.S: I see you do vids at UMD, I'm actually a student there, I'm using your videos to study for my 351 exam haha
@@mohammedarafat8059 hahahaha, hey, can you do me a favor and share the heap sort video in piazza? It'd be weird if I did it. Or not...I don't really care but I think it'd help many people.
@@BackToBackSWE I'm not on the piazza for this class, never signed up lol, but I sent your vids to a few ppl, one who knows you too btw, who are taking it. You should post the bubble and insertion sort vids on there tho bc those were really helpful for the practice exam. It's not weird if you're promoting a service you provide if its useful to the people you're promoting it to. Self promo is only weird if you're promoting a service in a setting where no one wants to hear it, and trust me the ppl in my class need your vids lol
@@mohammedarafat8059 Eh, I don't feel comfortable forcing it
Sir you are doing this analysis informally as you are using the average,then how can you write E[X]??
Because we know that E[X]=sum(x.P{X=x}).
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
For avg case, wouldn't the notation be sigma instead of O? Nice explanation though!
Does the value of 2 is user input?
Thank you so much
Beautiful👌👏👏
ye
you're amazing.
thx
hi can you help me about bubble sorting index complexity big O and omega / (a1,a2,...............................an) n>=2
wassup
You are great sir 😍.Love from India..
thanks
Well it is Gauß 🤣🤣🤣 9:38
Seems like this bug went unnoticed for 3yrs kappa
love u life saver
Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
good video :)
22:19
what did I do?
thanks bro
Any time
Awesome...
hey
why dont you before starting always remind people that the position of n is the index and it starts at 0 always, so we do i+1? i feel like a constant reminder would help. or maybe everyone knows this and I'm new so I need this but everyone else already ahead of me :D
When swap is done, i = i-1
what
amazing
thanks
ajmoooo majstorreeee
I'm so lost in all this :(
what is confusing, lemme know
So great