A Detailed Algorithmic Analysis of Insertion Sort. Best Case & Worst Case.
Ғылым және технология
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: Give exact comparisons and moves that happen in the best, average, and worst case of insertion sort.
Gauss' Trick: mathcentral.uregina.ca/qq/data...
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
Пікірлер: 153
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 KZread.
@rishabhjha447
3 жыл бұрын
kzread.info/dash/bejne/dINllpeBebiugso.html
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
4 жыл бұрын
hahahahaha, ok, I'm just a dude...and I'm wrong a lot
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.
These videos are so underappreciated. I can t believe it.
@BackToBackSWE
4 жыл бұрын
yo
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
21 күн бұрын
Fr. I hope to remember their names and donate when I make it
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
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
Bro you are doing a great job explaining all this. We appreciate the work you put in. Thanks again.
I love the way you explain things, the clarity is unmatched, thanks so much.
@BackToBackSWE
3 жыл бұрын
sure
I can't even express how thankful I am for your videos! They help me a lot in my studies! Your videos are amazing :)
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.
Superb analysis!!! I had been searching for such complete analysis for so long; finally got it here.
@BackToBackSWE
4 жыл бұрын
great
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!
Your attitude and presentation makes learning fun and clear. I wish you the best in your future endeavours. Liked and subscribed.
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.
you are so good in explaining things!!! THANK YOU so much for the videos!!!
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.
Thank you so much for this! Brilliant vid! Keep up the good work!
Thank you for this really perfect explanation !!
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 🌽🌽
Hats off to the best explaination on insertion sort
most videos and books did not indicate that A[0]=-infinity. This video really helps to understand. Thanks!
You are doing great! You are awesome at what you do!!! YOUR VIDEOS ARE SO DAMN HELPFUL! Keep up!
@BackToBackSWE
5 жыл бұрын
thanks
Yes this is EXCELLENT Work. Please continue. Thank you very much for your knowledge
@BackToBackSWE
5 жыл бұрын
thanks
You’re videos are really helpful ive got exam tomorrow and they’re helping
@BackToBackSWE
4 жыл бұрын
nice, umd?
Oh man! You can't tell how thankful I am for this video!
@BackToBackSWE
7 ай бұрын
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
Enjoyed the presentation. Explained clearly.
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
3 жыл бұрын
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
Man!!!! Best videos on algorithm ❤️
@BackToBackSWE
4 жыл бұрын
thx
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
THANK YOU!!!
cool explanation thanks.
Thank you for super great videos
broooooo.... duuuude!!!!! You're AMAZING. way better than my 50mins lecture
@BackToBackSWE
4 жыл бұрын
no u
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.
The only way to appreciate these videos for everyone is to share them. Come on guys lets show some appreciation
@BackToBackSWE
4 жыл бұрын
lol
The Grind! The hussle!
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
thank you so much :)
Kudos to you! Thanks!
@BackToBackSWE
5 жыл бұрын
ya
OMG... THANK YOU
a very useful one
Awesome,please do a video for finding the longest palindromic subsequence.
@BackToBackSWE
5 жыл бұрын
Yes, it's on the list, it'll come one day
Thank you very much for this useful video
@BackToBackSWE
Жыл бұрын
Glad it was helpful!
Great Video!
@BackToBackSWE
7 ай бұрын
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
Thank you so much
@BackToBackSWE
4 жыл бұрын
sure
Wow man great video.
@BackToBackSWE
4 жыл бұрын
thanks
it is most useful video ever.
@BackToBackSWE
5 жыл бұрын
haha bold statement
Your clarity is next level. Thank you. Great video, thumbs up and sub from me
@BackToBackSWE
Жыл бұрын
Thanks for the sub!
thaaaank you
You are awesome
Can you cover algorithm strategies: Brute Force, Greedy, Dynamic Programming, and Divide and Conquer?
@BackToBackSWE
3 жыл бұрын
maybe
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
Wonderful videos, it would be great if we have sequence number for Videos, to follow easily,Thanks
@BackToBackSWE
5 жыл бұрын
thx
is there a video where you explain the average case for insertion sort?
do the average case pls
Listening to this at 1.75 speed and enjoying it!
@BackToBackSWE
4 жыл бұрын
hahaha, I recommend everyone do that for learning vids. I do podcasts 1.5x and videos 1.5x-2x
@uzboxing5238
4 жыл бұрын
@@BackToBackSWE actually, after my comment I tried 2x too, very effective. Thank you for the videos. They are helping a lot!
@BackToBackSWE
4 жыл бұрын
@@uzboxing5238 nice
0:01 Rock on dude
@BackToBackSWE
4 жыл бұрын
what did I do
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 🙄😕
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?
What uni are you at?
@BackToBackSWE
4 жыл бұрын
This one umd.edu/
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
7 ай бұрын
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
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.
fine
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
I wanted the average case aaaa
Ben, love u 🤣 我想当你的小迷弟啊啊啊,Now, Let's deal with the sort problems
@BackToBackSWE
5 жыл бұрын
I want to be your brother too
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
Do you think you'll eventually do average case?
@BackToBackSWE
4 жыл бұрын
no, I should've but it sucks and would've added 30+ minutes to recording time, are you in 351?
u didnt do average case :( but otherwise great video.
@BackToBackSWE
5 жыл бұрын
I know :(
Can you add subtitle to these contents ?
I used to take Fawzi’s 250 in that classroom 😂
@lernordmac2711
4 жыл бұрын
You could see Stamp from the windows if it was daytime I miss it lol
@zkfdsldfjsdjfl1
4 жыл бұрын
@@lernordmac2711 YO the good times
@BackToBackSWE
4 жыл бұрын
yeah it is in ESJ, top floor, all the way to the left.
@BackToBackSWE
4 жыл бұрын
@@lernordmac2711 could u? I don't think u can but u can see Hornbake.
@BackToBackSWE
4 жыл бұрын
@@zkfdsldfjsdjfl1 yes
But what about average case
@BackToBackSWE
4 жыл бұрын
uh
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
plz attach java code
@BackToBackSWE
4 жыл бұрын
The repository is deprecated - we only maintain backtobackswe.com now.
System.out.println("Superb");
@BackToBackSWE
4 жыл бұрын
thx
did you listen to eminem new album? music to be murdered by?
@BackToBackSWE
4 жыл бұрын
yeah
Read About Islam bro and thank you for your great explaination❤❤
there was no average case. -.- i watched the whole video for average case but nope. -.-