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!

@BackToBackSWE

5 жыл бұрын

haha thanks

@spectermakoto9029

5 жыл бұрын

I hope not small niche channels are the best

@BackToBackSWE

4 жыл бұрын

@@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.

@BackToBackSWE

4 жыл бұрын

sure

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!

The most helpful video ever! Thank you for taking the time to do this.

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!!

@BackToBackSWE

5 жыл бұрын

sure, I think I'm in your class haha

Brilliance at its best. Good job man. Thumbs up as i understood the topic really well from your video

This is definitely one (maybe the one) of the best channel!

@BackToBackSWE

4 жыл бұрын

thx

Everything about this video is perfect. Thank you.

@BackToBackSWE

4 жыл бұрын

nice, u perfect

Awesome explanation!!!

Very ,very thorough explanation. Excellent.

I wish you and your channel the very best bro! 🙏🏽✨☝🏽🎊

this is just amazing , thank you

I chuckled when you said you weren't sure what Gauss' last name was. Nice video. Your content is awesome.

thank you so much.....this video helps me to understand the topic clearly.

@BackToBackSWE

4 жыл бұрын

great

This really helps me a lot. Thanks!

@BackToBackSWE

3 жыл бұрын

great

Keep the good work going on brother...

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

4 жыл бұрын

Thx and wym

@iambongani

4 жыл бұрын

@@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

You have become my fav teacher :)

You’re gonna get really big soon!

@BackToBackSWE

5 жыл бұрын

haha, maybe...maybe not. I'm content doing what I'm doing.

This video is very useful, thank you so much.

just found a great channel for algo and data struc

شكرا علي الشرح الوافي والممتع تحياتي من ليبيا

Please make videos on merge , quick sort and counting sort..

@BackToBackSWE

5 жыл бұрын

k

Thank you many times. You've been helping me a lot.

@BackToBackSWE

2 жыл бұрын

Thank you, we have got your back!! 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

Thank you so much

It's the best explanation. Thank you for sharing.

Greetings from Turkey, thank you for your nice explanation.

Great video as always

@BackToBackSWE

4 жыл бұрын

thx

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 .

@BackToBackSWE

4 жыл бұрын

I already did

very nice explaining ! thank u

@BackToBackSWE

4 жыл бұрын

sure

so much explanation. keep it up bro

@BackToBackSWE

5 жыл бұрын

thanks

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

Really love ur videos! best till now for me. Also, what is the name of the music at the end?

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

@BackToBackSWE

5 жыл бұрын

k

good video :)

So what will be the best case time complexity? Is it O(n^2) according to your algorithm?

@BackToBackSWE

3 жыл бұрын

Yes. O(n) is the best case for (modified) bubble sort if the array is already sorted, there is another video for that

Can you make a video on loop invariant ant

God bless you! You saved me!

@BackToBackSWE

4 жыл бұрын

ye

Another great video. What do you think about competitive programming?

@BackToBackSWE

5 жыл бұрын

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/

Beautiful👌👏👏

@BackToBackSWE

4 жыл бұрын

ye

in my opinion you are better than mit.Thankyou for depth

@BackToBackSWE

Жыл бұрын

Thank you Surendra 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀

I rarely write comments. But this video is very useful. Thank you so much for all the efforts and keep doing great content.

@BackToBackSWE

Жыл бұрын

Thank you, means a lot 🎉 You can also check out our free DSA course - backtobackswe.com/

you're amazing.

@BackToBackSWE

3 жыл бұрын

thx

love u life saver

@BackToBackSWE

Жыл бұрын

Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀

Does the value of 2 is user input?

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

@BackToBackSWE

4 жыл бұрын

I don't remember the math much in this video

@AARUSHPRATIMAYANK

4 жыл бұрын

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

Awesome...

@BackToBackSWE

5 жыл бұрын

hey

thanks bro

@BackToBackSWE

3 жыл бұрын

Any time

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).

@BackToBackSWE

4 жыл бұрын

This is too long to read (im fast replying to comments) but i love you

For avg case, wouldn't the notation be sigma instead of O? Nice explanation though!

How would you find the sum of possibilities if we had 6 different color on dice instead of 6 different numbers?

@BackToBackSWE

5 жыл бұрын

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.

amazing

@BackToBackSWE

4 жыл бұрын

thanks

Vry gud performance I likes it

@BackToBackSWE

4 жыл бұрын

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

@BackToBackSWE

5 жыл бұрын

I have done all of those.

@mohammedarafat8059

5 жыл бұрын

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

@BackToBackSWE

5 жыл бұрын

@@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.

@mohammedarafat8059

5 жыл бұрын

​@@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

@BackToBackSWE

5 жыл бұрын

@@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}).

@BackToBackSWE

4 жыл бұрын

I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.

hi can you help me about bubble sorting index complexity big O and omega / (a1,a2,...............................an) n>=2

@BackToBackSWE

4 жыл бұрын

wassup

Wikipedia says n# swaps for average is O(n) .. not O(n^2) why?

@BackToBackSWE

4 жыл бұрын

Can u link - not sure what you are referencing

@nabi7600

4 жыл бұрын

@@BackToBackSWE sorry it was n# comparisons

You are great sir 😍.Love from India..

@BackToBackSWE

5 жыл бұрын

thanks

22:19

@BackToBackSWE

4 жыл бұрын

what did I do?

Well it is Gauß 🤣🤣🤣 9:38

@_why_3881

2 жыл бұрын

Seems like this bug went unnoticed for 3yrs kappa

When swap is done, i = i-1

@BackToBackSWE

4 жыл бұрын

what

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

ajmoooo majstorreeee

I'm so lost in all this :(

@BackToBackSWE

3 жыл бұрын

what is confusing, lemme know

So great