A Detailed Algorithmic Analysis of Insertion Sort. Best Case & Worst Case.

Подписаться 241 тыс.

Просмотров 52 тыс.

50% 1

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Give exact comparisons and moves that happen in the best, average, and worst case of insertion sort.
Gauss' Trick: mathcentral.ure...
Bubble Sort Analysis: • An In-Depth Algorithmi...
I'm so sorry that my camera was about to die. I had to cut the video short. The average case is the hardest part to understand so this video also would have been much longer.
I'm not sure if I will ever cover it in a video...so there's a really hard challenge. What's the amount of comparisons and moves for the average case? (the hard part is calculating the expected value for the total while loop comparisons)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech

Опубликовано:

9 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 153

@BackToBackSWE 5 лет назад

Table of Contents: We Have Come A Long Way pt. 1 0:00 - 0:37 Behind The Scenes 0:37 - 1:00 We Have Come A Long Way pt. 2 1:00 - 1:23 What We Are Going To Cover In This Video 1:23 - 2:02 Walking Through The Pseudocode 2:02 - 3:08 What Is A Sentinel? 3:08 - 3:37 The 2 Fundamental Operations: Moves & Comparisons 3:37 - 4:59 Starting The Actual Insertion Sort Walkthrough 4:59 - 14:25 Best Case: Exact Amount of Comparisons 14:25 - 17:28 Best Case: Exact Amount of Moves 17:28 - 21:08 Worst Case: Exact Amount of Comparisons 21:08 - 28:55 Worst Case: Exact Amount of Moves 28:55 - 34:45 Sorry...The Camera Was About To Die 34:45 - 35:06 Wrap Up 35:06 - 36:19 The code for this problem is in the description. Fully commented for teaching purposes.

@rishabhjha447 3 года назад

Watch Ravindra Babu Ravula's Video on RU-vid.

@rishabhjha447 3 года назад

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-BO145HIUHRg.html

@sushruttabakade6088 5 лет назад

I'm crying here, for the past one hour I was struggling with all of these complex concepts and how wonderfully you in just half an hour taught me everything. Thank you man, excellent video!

@BackToBackSWE 5 лет назад

hahahahaha nice.

@dreamzsiva 5 лет назад

I love how this young guy who is still pursuing his degree is so well articulated in his thoughts as a teacher and proficient as a coder. You will go a long way buddy! I am buying your interview class.

@BackToBackSWE 5 лет назад

hahahahaha, ok, I'm just a dude...and I'm wrong a lot

@mariasandru5566 5 лет назад

These videos are so underappreciated. I can t believe it.

@BackToBackSWE 5 лет назад

@dead_gawk 6 месяцев назад

The thought of putting in 6 hours of work everyday, just so that some random person on the internet would get free education is amazing. Respect to you, Champ.

@tegathemenace Месяц назад

Fr. I hope to remember their names and donate when I make it

@fortresssanitarium2205 3 года назад

This is what I'm talking about when I tell my parents what a teacher should be like. The passion that u display is alluring. Thanks for doin this buddy

@superchillh3o 3 года назад

I love the way you explain things, the clarity is unmatched, thanks so much.

@BackToBackSWE 3 года назад

sure

@GamerGabbar 5 лет назад

THANK YOU SO MUCH FOR MAKING VIDEOS LIKE THIS! I'm an Indian but I don't live in India and most videos like these are made by people from india, They're excellent videos but hard to understand. This is super nice! Again, Mad Thanks! 🙏

@BackToBackSWE 5 лет назад

Nice sure

@leahkelley8452 5 лет назад

I am a CS major and your videos have honestly clarified the majority of the concepts that my professors failed to teach. Thank you for doing this. It is extremely helpful. :)

@BackToBackSWE 5 лет назад

I think we are in the same class probably. I go to UMD. In algos rn.

@leahkelley8452 5 лет назад

Why are you in algorithms? I thought you were a grad student?

@BackToBackSWE 5 лет назад

I'm a 2nd year.

@leahkelley8452 5 лет назад

Are you in Teli’s class? Did you transfer from a different school? ... what is your name?

@BackToBackSWE 5 лет назад

Yes. I'm in your class probably haha. Section #0201. My name is Ben.

@techservices7028 7 месяцев назад

most videos and books did not indicate that A[0]=-infinity. This video really helps to understand. Thanks!

@anrihek5701 5 лет назад

351 has just been such a confusing thing for me, even though I take a lot of notes and read through them I just don't get it. The analysis videos have been really helpful and they are much easier to understand than lectures. I know making these videos must be really time consuming and youtube channels seem to grow really slow sometimes, so I just want to say again how much I appreciate this and your work has been so meaningful.

@BackToBackSWE 5 лет назад

sure. Yeah, I assume you have Teli...I personally like Teli as a fundamental human being but his speed sometimes loses people. The problem is conceptual examples. If you speak what you see in your head...you have very few sentences before you begin to lose half the audience who weren't paying attention to your entry into a conceptual explanation...if that makes sense. This is why, when teaching it is critical to use visuals, be slow, and make sure that what is in your head...is on the board...not in words. Words lose people.

@warrenbinder3612 3 года назад

This is one of the best and most detailed videos about the best and worst cases of Insertion Sort. You explained the topics really well, they were easy to understand. F in the chat for your camera battery, the average case sounds interesting!

@BackToBackSWE 3 года назад

Glad it was helpful!

@NasK330 9 месяцев назад

Oh man! You can't tell how thankful I am for this video!

@BackToBackSWE 9 месяцев назад

Happy Holidays 🎉 And we are thankful for your comment, NasK! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

@bronzebond4869 3 года назад

Bro you are doing a great job explaining all this. We appreciate the work you put in. Thanks again.

@zainabsherani8950 5 лет назад

You're in my Algorithms class!!! WOW! Keep up the good work! The analysis portion helped me out!

@BackToBackSWE 5 лет назад

Hey, good. Sometimes I wish I could go up there and hammer out tiny things I KNOW are confusing students. Everything should be taught the way a student can pick it up quickly. I wish I could post in Piazza, but I don't wanna spam people. But I really think these videos would help people. I want to do a video for every lecture topic we do.

@vineetsharma4121 4 года назад

Superb analysis!!! I had been searching for such complete analysis for so long; finally got it here.

@BackToBackSWE 4 года назад

great

@KixMayne91 4 года назад

OMG I EFFING GET IT!!!!!!! Thank you so much, it was throwing me off thinking that the while loop was always supposed to execute n-1 time since its still a linear process. But now that you clarified it, will ONLY execute n-1 times if it never performs the swap operations. Other wise its performing n(n-1)/2 when it compares and swaps and compares again, etc... Thus making N^2 the average case since there will be moments where the comparison and swap occurs in an unsorted array.

@BackToBackSWE 4 года назад

great lol and tldr tbh im fast replying to comments I luv u tho but I dont remember any specific math it is very much on the spot

@maike3530 Год назад

I can't even express how thankful I am for your videos! They help me a lot in my studies! Your videos are amazing :)

@fabriciopolicarpo3725 3 года назад

You gave me keys bro. up to now I understood everything but that forsaken arr[j + 1] = current. Now I understand the entire algorithm mechanics.

@margaritasmoliakova7084 2 года назад

you are so good in explaining things!!! THANK YOU so much for the videos!!!

@supamdeepbains5172 4 года назад

You’re videos are really helpful ive got exam tomorrow and they’re helping

@BackToBackSWE 4 года назад

nice, umd?

@js4466 2 года назад

Your attitude and presentation makes learning fun and clear. I wish you the best in your future endeavours. Liked and subscribed.

@iambongani 4 года назад

The only way to appreciate these videos for everyone is to share them. Come on guys lets show some appreciation

@BackToBackSWE 4 года назад

lol

@joel_b9216 4 года назад

broooooo.... duuuude!!!!! You're AMAZING. way better than my 50mins lecture

@BackToBackSWE 4 года назад

no u

@zeffanayahyisrael8428 5 лет назад

Yes this is EXCELLENT Work. Please continue. Thank you very much for your knowledge

@BackToBackSWE 5 лет назад

thanks

@lorenzozuluaga4309 5 лет назад

wow lend me tell you you got a new subscriber, really apprecciate that you give to us all this knowledge, bless from colombia!!

@BackToBackSWE 5 лет назад

hahaha wassup from america 🌽🌽

@aaishikighosh6154 3 года назад

Tysm for this.... I am 18 and I am starting out on these subjects... Nd you really make these easier to understand...

@BackToBackSWE 3 года назад

great - you can go so far in this space, get good young

@fredericoamigo 11 месяцев назад

Thank you so much for this! Brilliant vid! Keep up the good work!

@hakancemgercek 5 лет назад

14:10 I'm brave enough to stay with this video because I'm trained to stay in the class while the tutor told everything which I didn't understand about this course XD. But thanks to you now everything "finds a home" in my brain. THX

@BackToBackSWE 5 лет назад

thanks

@khadijaanam62 5 лет назад

You are doing great! You are awesome at what you do!!! YOUR VIDEOS ARE SO DAMN HELPFUL! Keep up!

@BackToBackSWE 5 лет назад

thanks

@procode6881 3 года назад

Hats off to the best explaination on insertion sort

@sohanaggarwal8770 2 года назад

Enjoyed the presentation. Explained clearly.

@cameronsantiago3155 2 года назад

The Grind! The hussle!

@Happy-on2is 4 года назад

Hii Mr I got a doubt 🤔🤔 actually in worst case moves it is 1 + (summation of i = 2 to n) 2 + (summation of j = 1 to i - 1) i right ??? but you have mentioned 1 + (summation of i = 2 to n) 2 + (summation of j = 1 to i - 1) 1 difference is the last 1 and i in the above expression

@BackToBackSWE 4 года назад

im not sure - I don't remember the math

@Happy-on2is 4 года назад

@@BackToBackSWE 🙄😕

@guowanqi9004 5 лет назад

6:09 29 will trample over 10's value. 6:24 10 is still looking for a home. Dang that seems so sad

@BackToBackSWE 5 лет назад

indeed

@user-yb6oc4tj2w 4 года назад

Man!!!! Best videos on algorithm ❤️

@BackToBackSWE 4 года назад

thx

@nadasa208 3 года назад

Thank you for this really perfect explanation !!

@vishwassrinivas474 5 лет назад

Awesome,please do a video for finding the longest palindromic subsequence.

@BackToBackSWE 5 лет назад

Yes, it's on the list, it'll come one day

@osandarathnayaka9002 3 года назад

cool explanation thanks.

@zaintahir3348 Год назад

THANK YOU!!!

@cerenarkac3484 2 года назад

Thank you very much for this useful video

@BackToBackSWE Год назад

Glad it was helpful!

@favour_republic 9 месяцев назад

If only Nigeria lecturers teaches this way... The problem now is I understand yours but it's totally different from what I was taught in class and the lecturer expect me to write the exact thing he taught in class 😢 if not I'm not getting my full mark... Anyways thanks this your video was very helpful 🎉

@BackToBackSWE 9 месяцев назад

Happy Holidays 🎉 What's important is getting your concepts clear! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

@sajidsarkar9574 3 года назад

Can you cover algorithm strategies: Brute Force, Greedy, Dynamic Programming, and Divide and Conquer?

@BackToBackSWE 3 года назад

maybe

@andrewnguyen6396 3 года назад

thank you so much :)

@Rahul-yg5kp 4 года назад

Wow man great video.

@BackToBackSWE 4 года назад

thanks

@esraataher36 3 года назад

a very useful one

@faysalahmedakash7703 3 года назад

why the number of comparisons for worst case is not "n(n-1)/2" ? Won't the ith element do (i-1) comparisons to get into the 1st position?

@AK-cl8iv Год назад

reference: when i = 2, j = 1,0 ; i = 3, j = 2,1,0.... i = n, j = i-1, i-2,...,0 hence total number of comparisons for worst case is 2 + 3 + ... + n = n(n+1)/2 -1

@laggynacho 9 месяцев назад

Great Video!

@BackToBackSWE 9 месяцев назад

Happy Holidays 🎉 Thank you for your kind words! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

@paulpassiglia9997 4 года назад

Thank you so much

@BackToBackSWE 4 года назад

sure

@thanhtungtran8249 3 года назад

Thank you for super great videos

@ashishm8850 5 лет назад

Kudos to you! Thanks!

@BackToBackSWE 5 лет назад

@noursafa22 Год назад

do the average case pls

@alirezaRahmanikhalili 5 лет назад

it is most useful video ever.

@BackToBackSWE 5 лет назад

haha bold statement

@booboo-oh1vd 3 года назад

OMG... THANK YOU

@SumayahAlsakiti 11 месяцев назад

thaaaank you

@lernordmac2711 4 года назад

0:01 Rock on dude

@BackToBackSWE 4 года назад

what did I do

@sujithkrishnan6429 5 лет назад

Wonderful videos, it would be great if we have sequence number for Videos, to follow easily,Thanks

@BackToBackSWE 5 лет назад

thx

@JustJoelTV 2 года назад

Your clarity is next level. Thank you. Great video, thumbs up and sub from me

@BackToBackSWE Год назад

Thanks for the sub!

@alannah000 Год назад

You are awesome

@uzboxing5238 5 лет назад

Listening to this at 1.75 speed and enjoying it!

@BackToBackSWE 5 лет назад

hahaha, I recommend everyone do that for learning vids. I do podcasts 1.5x and videos 1.5x-2x

@uzboxing5238 5 лет назад

@@BackToBackSWE actually, after my comment I tried 2x too, very effective. Thank you for the videos. They are helping a lot!

@BackToBackSWE 5 лет назад

@@uzboxing5238 nice

@saadmahmood5396 3 года назад

is there a video where you explain the average case for insertion sort?

@loganynguyen 4 года назад

What uni are you at?

@BackToBackSWE 4 года назад

This one umd.edu/

@CarolinaRutiliLima 5 месяцев назад

I wanted the average case aaaa

@JustSoji 4 года назад

How different are comparisons and moves if we don’t use a sentinel

@BackToBackSWE 4 года назад

what do you mean "how different"

@JustSoji 4 года назад

Back To Back SWE will the number of moves/comparisons change if we don’t use a sentinel

@laxmipoojaanegundi7757 4 года назад

Can I be part of Back To Back SWE? I can assist in any work. Its so exciting to be part of Back To Back SWE

@BackToBackSWE 4 года назад

Yeah, I'm looking for writers that are good

@viktorvostrikov9625 5 лет назад

Thanks! Amazing series.., I watched bubble sort, but I still can't understand why you do you get (n-1) from the while loop set? How can you calculate bounds and say that it answer is n-1? Why when you can't use same approach if outer loop would not be 1?

@BackToBackSWE 5 лет назад

can you timestamp it?

@viktorvostrikov9625 5 лет назад

@@BackToBackSWE 16:30

@BackToBackSWE 5 лет назад

@@viktorvostrikov9625 Ok so best case comparisons. We get n - 1 since that purple section will get hit n - 1 times and NEVER get entered in the best case (the array is already sorted...nothing needs to go backwards for insertion).

@viktorvostrikov9625 5 лет назад

@@BackToBackSWE yes I get that, you will do only one comparison in for loop. and after all comparisons the purple area will be hit n-1. I just don't get the math of it and how you managed to convert Set from j=2 to n, to be equal to n-1. I thought that set supposed to mean 2,3,4,5,6...n. So you should sum all that and then you will get complexity, which is different than n-1.

@BackToBackSWE 5 лет назад

@@viktorvostrikov9625 If j goes from 2 to n, how many iterations happen? Imagine n is 3: j = 2 j = 3 2 iterations. n was 3. So n - 1 iterations that the if statement is hit.