Insertion sort algorithm

[@mycodeschool]

For average case, we can assume that T(n) = (c1+c3)*(n-1) + {1+2+3+4+ ... +n-1}*(c2/2) . We can assume that inner loop will run i/2 times for each i, and not i times. So, 2nd term in expression will be n(n-1)*c2/2 .. Still it will be something like an^2 + bn + c

[@user-wb5ox7nw2u]

RIP

[@azimharis2871]

@@user-wb5ox7nw2u bro the narrator didnt die, he is alive and kicking and is currently working for Google. His friend, whom he started the project with, sadly passed away

[@vinayshukla6316]

Even after 7 years, It is the best explanation out there.

[@shuvbhowmickbestin]

true

[@Smithy0013]

So this really was just a big build up to using the phrase A[hole]

[@jiganeshpatil1472]

04:22 So u dont keep searching guys.

[@julcaos]

no swearing gentlemen!

[@shivanshpachauri2855]

When I put the A[hole] in the hole

[@pokemaster1359]

RIGHT!! LOL I noticed it right off bat!

[@AnthonyFinix]

Eyyeee... Padayi pe dyan do.. :p

[@musicalismagical6373]

Thankyou so much sir I wasted my 5 hours in staring the notes given by college ... Suddenly after being fed up i looked at my phone n thought to see videoo. Within 45 min I understood everything and even I practiced it too .. Tysm

[@annanyshankertandon3513]

Hey did you get the job

[@ninjaweave8779]

I have my algorithmics exam tomorrow and your videos have helped me a whole lot more than any of my lecturers ever have... thanks so much, keep up the good work :)

[@ishanpand3y]

Thank you so much, sir. This channel is going to help future kids too, who will be willing to learn deep concepts of Data Structures.

[@maitrekpatel]

yeah its helping

[@ashwaniraj698]

thanks mycodeschool, you are the best mentor I have ever experienced. never able to get insertion sort from anyone. you made it so so clear. thanks man..

[@nmn02]

Rather than filling those holes we can simply swap elements as shown in the code. This will ultimately lead to the same thing. CODE:- void insertionSort(vector&v){ for(int i=1;i0&&v[hole-1]>value){ int temp=v[hole]; v[hole]=v[hole-1]; v[hole-1]=temp; hole--; } } }

[@codingnewbie925]

I thought of same but here we are swapping in every iteration of while loop which makes it less efficient

[@asmaithabteghiorghis3060]

Every necessary fact bundled as a 14 minute video. Excellent, and super amazing explanation. I am a big fan of your lectures.

[@rittuupreti5597]

R.I.P for this guy ..may he rest in peace ..he did a lot for the community 🙏

[@akshatpandey2256]

Where is he?

[@6srer]

He's dead???

[@FearAwaits]

He's not​@@6srer

[@manojlakhera9713]

what?

[@VashishthaKM]

​@@6srer hit and run 😣

[@danishazad1]

I am learning so many things from this channel...!! i just download all these videos and watch in faster mode!! Thank you so much sir it helps me a lot.

[@hirakmondal6174]

The way Indians are spreading E-education and making such wonderful videos I think that India will rule the e-learning market after a few years... great work guys.. carry on.. :) Top 10 Growth Rates By Country. Growth rate shows how each country adopts eLearning and is a significant indicator since it can reveal revenue opportunities. The growth rate of self-paced eLearning by country is : India: 55% China: 52% Malaysia: 41% Romania: 38% Poland: 28% Czech Republic: 27% Brazil: 26% Indonesia: 25% Colombia: 20% Ukraine: 20%

[@Kgotso_Koete]

I really can't wait for this to happen. The quality of teaching from Indian programmers is so gooooooood!

[@pegasus7118]

The east is rising again and taking is rightful place in the world. For most of the world's history, it was the orient, and some successful old world civilizations like that of Iraq and Egypt that were the centres of learning. The west completely dominates Eastern Europe and the Middle east today but the orient is coming back with a bang!!

[@amritprusty6097]

HIRAK MONDAL stop making this political

[@user-jd1zx]

did you use insertion sort to get the countries in ascending order?

[@prince5922]

you really pulled those numbers out of your pathetic ass

[@HarpreetBedi01]

Nice explanation. On an fun note. "A[hole]" hehe, its interesting you went with this nomenclature for insertion sort.

[@mycodeschool]

Harpreet Bedi I am surprised how this comment is coming so late ;)

[@saurabhshrivastava224]

Well that is called observation....

[@alekssandroassisbarbosa9570]

+mycodeschool Please, I have a doubt: we do not count the first "for"? I got T(n) = (c1+c3)(n-1) + [n(n-1)/2].c2 + n neither array indexing ?

[@pritamsarkar8830]

Here he counted the T(n) of only for the shorting method.....because taking array as input is a constant case for all sorting processes, I think so

[@priyanshujoshi6999]

Harpreet Bedi very true

[@vidyamadineni6590]

I am very intrested by listening ur class it was soo helpful tqq....☺☺☺

[@mridulrajbhar12]

i just got it in 30 minutes thank you your channel is 7 years older but still best

[@burdmate]

He keeps inserting into different holes. Or A[holes], which is worse. This algorithm is rather promiscuous.

[@thewatcherlollol]

lol

[@hunainalikhan9253]

His explanation make me love for coding. I'm still shock for his tragic loss a gem programmer community just lost.

[@beosoftlabs]

You are definitely in number oneth position in explaining algorithms

[@its.moonjc]

This algorithm is a pain in my A[hole].

[@GokulRG]

Best comment ever!!!

[@vikasjaiswal7821]

take a pain killer

[@jefflgaol3448]

good one

[@Play4peace]

Still in 2020 😑

[@ryan-bo2xi]

hey just checking .. is the pain gone ? It's like three years now ..

[@sumitwadhwa8823]

so basically, on each iteration, we swap in reverse order and pushing smallest element at the start of array: for( let i = 1, len = arr.length; i < len; i++ ) for( let j = i; j > 0 && arr[j-1] > arr[j]; j-- ) swap(arr, j-1, j);

[@satejbidvai]

This is the first time I actually understood Insertion Sort. Thanks !

[@俊材刘-n6m]

its my first time to make comment, it's a a very clear explanation, illustrating every small step, thank you very much!

[@HasXXXInCrocs]

Holy crap, just noticed all your videos are in 21:9. How glorious!! This is some masterrace shit right here. Love seeing it on my ultrawide monitor.

[@MegaMsanand]

Great explanation! The following code (C++) can also be used as an alternative, which basically a roughly condensed version of your code. This places an element in an array in its right place, everything within one loop. No new variables, no new assignments. Anyway, love your videos! #include using namespace std; int main() { int n; coutn; int A[n]; cout0){ int x=A[i-1]; A[i-1]=A[i]; A[i]=x; i--; } } cout

[@_manish519]

Your for loop runs n^2 times as you are decrementing 'i'. This increases time complexity.

[@vinhnguyen-o5z]

you are chipping i away, how will this help

[@GetUpAndWatchVideos]

Good code, but like mentioned in a reply above, you are decrementing the value of 'i' in the while loop, so it's going to never reach the end of the for-loop, as 'i' is also the loop-variable, resulting in an infinite loop. Fix to this: Similar as in the video; make a hole variable, assigning it the the value of 'i', and you change all the 'i' variable instances, in the while loop, for the hole variable. This way you can avoid infinite for-loop.

[@pranshul67]

Wow! what an amazing way to demonstrate the insertion sort. I am so glad I stumbled upon this video. Great job on the explanation. Thank you so much. Mycodeschool tutorials are in my opinion, the best videos for budding programmers.

[@syedfuaad1910]

Spent hours trying to understand this cleared it up thanks

[@jakeDragonaire]

To anyone who found the A[hole] hard to grasp (pun not intended), here is a slightly different implementation: //We need to compare the last element as well with its previous ones, useful in worst case scenarios like 5 4 3 2 1, // where 1 needs to go all the way back to leftmost index. for i=1 to i=0 && temp

[@ashutoshverma1418]

def insertion(arr): left=0 right=1 element=arr[right] while right>len(arr): while left>=0 and arr[left]>arr[right]: arr[left+1]=arr[left] left-=1 arr[left+1]=arr[right] right+=1 left=right-1 return arr

[@21agam]

Mind blowing video man,indian teacher are best

[@muhammadadnanakmal9590]

ya agree with you

[@Kgotso_Koete]

My sentiments exactly.

[@chiefjudge8456]

No they're not. Don't be racist.

[@thewatcherlollol]

@@chiefjudge8456 how is that racist?????

[@dhananjayagarwal9905]

i believe you need to change thecondition in outer for loop. it should run till N time instead of N-1 as you are already starting At 1 position. In current situation the last element in array will not be sorted(considering condition as i

[@Imafriggingoddess]

Made my life a whole lot easier. Thanks.

[@chaosinorderrr]

hole lot easier

[@supritkumar3161]

your tutorial is the best one on youtube... A big THANK YOU sir..

[@kbz313]

I love mycodeschool tutorials. Keep up the good work.

[@ravivarmachaluvadi9158]

Love you bro , the way you’re explaining and the tools using for it is mind blowing, keep it up 🙏🏻

[@kartikeyasrivastava4798]

you have explained all algorithms perfectly

[@rohitpandey4411]

Best and simplest explanation sir,hats off to you

[@samratsinghrathore7240]

This video is just great Many videos were made but i search for this video whenever i forget the algo

[@JeffreyMyersII]

lol A[hole]. Very good video though. You teach better than my professor.

[@zaheerkhan-ku5wd]

Jeffrey Myers II

[@0215story]

That's a sad story..but true...

[@CamKnoppMusic]

Came here looking for this comment

[@anamigator]

This explanation is quite simple and intuitive. Great job and thank you :)

[@kartikxramesh]

Love the use of your illustrations, very helpful video!

[@shashankpathak63]

please make a playlist of all the important algorithms sir . Your videos are very helpful

[@shivamgohel8400]

you should also talk about the space complexity in big-O notation...

[@harennagdewani6503]

7th Line: A[hole] = value is not required. As, the value on A[hole] will automatically be smallest if we are continuosly swapping values of hole-1 and hole in while loop

[@Whiteroca]

Thank you sir! You helped me understand insertionSort in 6 minutes of your video.

[@mikeyyychang8402]

simple java code: public static void insertionsort(int[] arr) { // idea is to insert the data in between next one so one for loop one while loop int n = arr.length; for(int i = 1;i=0 && arr[j]>compare) { arr[j+1]=arr[j]; //if left>right swap j = j-1; //* $01 // $10 // 1$0 (if still need to swap) // by keep swapping it will like an insertion // but actually pushes all the data bigger/smaller to the next position } arr[j+1]=compare; } }

[@ntrrakesh2887]

Super broo

[@SmartProgramming]

brilliant, easy to understand, thank a lot sir 👍👍

[@kishanpareek2848]

There are so many tutorials out there but no one is at par with mycodeschool. How many are watching this in 2021.

[@drekevans]

wish i would have found these videos at the begging of this semester instead of for the final

[@akaashraj8796]

cant belive this vedio is 10 years old, great vedio

[@jamyrahman3588]

Thanks Bro I was trying to understand this particular code about 1.30 hours> while(1) {thanks for your simulation}

[@Nicothefunky]

Hello, first many thanks for your VERY helpful video's! You're helping me out a LOT for my examinations. But I've got a question, I don't get how go from '1+2+3+...+n-1' to (n*(n-1))/2

[@mycodeschool]

Nicothefunky 1+2+3+ ... +n is an arithmetic progression. Sum of an arithmetic progression would be (n/2)*(2a + (n-1)*d) where a = first element, n = number of elements, and d = difference between two elements. for something like 1+2+3+... sum would be (n/2)*(2+ (n-1)*1) , d = 1).. so if you would solve it it would be n*(n+1)/2. This is a standard formula for finding sum of first n natural numbers.... Now in this case, we are going only till n-1.. we have 1+2+3+.... + n-1 , so for this one,, sum will be (n-1)*(n-1+1)/2 i.e n*n(-1)/2 ...

[@palagatideepthireddy3659]

what your explaining is clean and clear,nice teaching

[@FunRunsafi]

Tomorrow is my ppr thanks man ❤️

[@muhammadarslanbhatti2139]

should be ' i < n ' , otherwise it doesnt access the last element in the array

[@Jamil-Tech]

“I have always liked the stories where an underdog wins. I just want to be part of one of those stories.”, A great teacher once said. Rest in Peace, Sir.

[@eligirl100]

Something was weird for my code. It works if i set i < n and hole > 0 or if i < n - 1 and hole >= 0

[@ChandraShekhar-by3cd]

Best Explanation Ever!!..Please post more videos on Design Patterns using C++ ..That will be a great help

[@findoc9282]

A little mistakes: you should include "A[hole] = value" into the while loop, so it can keep comparing and updating in a sigle "hole adjustment"

[@vigneshbalasubramanian7878]

No need cuz he is using the variable "value" for comparing. I think that should suffice

[@nandgopaldevnath8242]

a[hole]=value; should be within while loop check for e.g 3,8,2,5,9.Output will be 3,2,5,8,9. for(i=1;i0 && a[hole-1]>a[hole]){ a[hole]=a[hole-1]; hole=hole-1;a[hole]=value; } }

[@mycodeschool]

yeah sure, we will get them all. :)

[@venkatesh3439]

thank you very much sir the way you explain the logic is very simple to understand!!!

[@ChowtapalliSreenivas]

Presentation was crisp and addressed the need

[@music-mw3qt]

Your explanation is quite good

[@mithunshaha4342]

very very thankyou sir.your tutorial is really helpful for me to understand case analysis of sorting algorithm'

[@harshitsangwan890]

Thank you so much ! It was pretty easy to understand using your simple yet elegant explanations :)

[@VivekSharma-bl7ul]

wonderful sir , i am really impress your teaching method

[@superparkourist215]

You have subtitles over important parts the video that cover the psuedocode. We don't need subtitles! We understand you just fine!

[@jayeshsonkusare3087]

Yeah ur right

[@lokeshaggarwal5129]

good work guys, this video is so helpful for me to understand the logic of sorting .

[@FutureAITrend]

Please continue creating videos , like your approach

[@ubernerrd]

Thank you for making these videos. You are a great instructor.

[@sircatbear5886]

You have explained it so well! Thank you!

[@WimpyWarlord]

How pure of a person you are, went through the entire algorithm without even realizing the pun.

[@GYANESHWAR27]

Great Algorithm explaination.THANK YOU SO MUCH to make it easy.!

[@lakshminarasimmanv]

Thanks for the same problem found in Introduction to algorithms book.

[@VashishthaKM]

Best utilisation of these lectures if you consume with... Introduction to Algorithms by CLRS.❤

[@gowthamannarayanan361]

Hi, Learning is damn good and it is very easy to grasp. Am just sharing the actual logic of insertion sort. Correct me if am wrong. public static int[] insertionSort(int[] input){ int len =input.length; for(int i=1;i0){ if(input[hole]

[@ronakpatil6081]

this is really the best explanation

[@prestonip]

This video is so good it made me cry

[@MsWonderlands]

Listening to all your sorting algorithms, I have a thought/query: our final intent is same as to sort, but how do we remember the individual algorithms (bubble, selection, insertion...? ) or at least differentiate them while choosing or implementing? Thanks.

[@ritikshrivastava9442]

great explanation but still i need to learn this but i if forget then i can make it bcoz your explanation is quite good

[@azimroydar1083]

Your videos are very clear and helpful.thanks alot

[@xiaofeiluo7463]

the "hole" part is a bit confusing, it's just a swap between the current element and the elements on the left side which are greater than that current element. Here's my implementation in java, using swapping: public static void sort(int[] a) { int n = a.length; for (int i = 0; i < n; i++) { for (int j = i; j > 0 && a[j] < a[j-1]; j--) { swap(a, j, j-1); } } }

[@saddatsabanature4307]

best i didn't expect .....(10 years ago but still best explanation)

[@giorgi23]

Your explanation is really helpful. Good job!!!

[@jawad9757]

Awesome video, especially with all the other sorting algo videos.

[@mohammedzeeshan146]

Lucid explanation . Awesome work guyz.

[@kalaimanigovindasamy2205]

Very nice explanation sir about sorting

[@shawonsarker4384]

so nice tutorials sir... thanks for your all tutorials

[@gustavobertolino400]

Excellent explanation using intuitive example first and pseudo-code then. Thanks, man, and keep doing helpful tutorials like that!

[@adityasrivastava5968]

Sir, why did you stop uploading video?Such good explaination.

[@abhishekbhadoriya9333]

I was looking for same answer bro- then I read this www.freecodecamp.org/news/mycodeschool-youtube-channel-history/, felt very bad :(

[@fengqichen8432]

thank you for your intuitive explanation, sir.

[@sanketughade6986]

instead using the inner while loop we can also use a for loop there it makes the code pretty easy.

[@TEXAS2459]

am i the only one who realized that he taught us how to manage the Ahole????.........we learned a program about Aholes common i mean.........

[@anahitasaxena9439]

Thank you so much . This video was really helpful, helped me visualize the logical aspect of if very well

[@nandini2907]

Sir your vedios are very good for learning ds and understandable Sir can you provide vedios on java ?we want java lectures .

[@ngozik-opara4373]

This is cool, you are a great teacher.

[@jaypatel8131]

thanx bro even i dnt hav book u help me a lot.👍

[@beautifullifejourney28liza]

Very nice explanations...thank you so much

[@rafaelfonseca7942]

Good job master! I really appreciate it... you have got a new subscriber!

[@aakashjain5999]

thank you for such nice videos. please make videos on dynamic programing and graph theory algorithm.