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 man, I just wanted to take the time to appreciate your teaching skills, it is a gift. you literally just taught someone who does not have a degree in anything but passionate about Software development bubble sort and mathematics, truly appreciate your work a lot. If you need people to mentor please let me know I am in
@@BackToBackSWE I mean, I just started learning how to code with a remote school and solving algorithms is one of the biggest things I really want to be good at. I am a step by step kind of a person. I don't like cramming things but I want to know the in depth. Just like your classes. So if you ever want to teach a beginner I am available. Or if you have material I can buy from you that you wrote please I'd like to support your movement
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
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).
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
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
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
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.
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
