Insertion sort algorithm

[@vinayshukla6316]

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

[@shuvbhowmickbestin]

true

[@mycodeschool]

You can write to mycodeschool [AT] gmail [DOT] com. See "About" of the channel for more details.

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

[@b2-mani]

RIP

[@azimharis2871]

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

[@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 :)

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

[@annanytandon]

Hey did you get the job

[@asmaithabteghiorghis3060]

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

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

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

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

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

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

[@mridulrajbhar12]

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

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

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

[@俊材刘-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.

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

[@vidyamadineni6590]

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

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

[@satejbidvai]

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

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

[@xTyler73]

Doesn't work when array is in reverse order, int j = 5; for(i = 0; i < 5; i++){ j--; a[i]=j; } then a call to your function as described at 8:32, prints the following: 1 2 3 4 0 //where 0 is garbage value? fixed by changing the for loop to for (i = 1; i

[@beosoftlabs]

You are definitely in number oneth position in explaining algorithms

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

[@hunainalikhan9253]

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

[@kbz313]

I love mycodeschool tutorials. Keep up the good work.

[@Imafriggingoddess]

Made my life a whole lot easier. Thanks.

[@chaosinorderrr]

hole lot easier

[@burdmate]

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

[@thewatcherlollol]

lol

[@Whiteroca]

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

[@syedfuaad1910]

Spent hours trying to understand this cleared it up thanks

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

[@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);

[@ravivarmachaluvadi9158]

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

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

[@SmartProgramming]

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

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

[@kishanpareek2848]

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

[@mycodeschool]

yeah sure, we will get them all. :)

[@kartikxramesh]

Love the use of your illustrations, very helpful video!

[@anamigator]

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

[@supritkumar3161]

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

[@rohitpandey4411]

Best and simplest explanation sir,hats off to you

[@kartikeyasrivastava4798]

you have explained all algorithms perfectly

[@akaashraj8796]

cant belive this vedio is 10 years old, great vedio

[@drekevans]

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

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

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

[@jamyrahman3588]

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

[@FunRunsafi]

Tomorrow is my ppr thanks man ❤️

[@samratsinghrathore7240]

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

[@ronakpatil6081]

this is really the best explanation

[@FutureAITrend]

Please continue creating videos , like your approach

[@palagatideepthireddy3659]

what your explaining is clean and clear,nice teaching

[@music-mw3qt]

Your explanation is quite good

[@sircatbear5886]

You have explained it so well! Thank you!

[@jawad9757]

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

[@harshitsangwan890]

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

[@ChowtapalliSreenivas]

Presentation was crisp and addressed the need

[@ChandraShekhar-by3cd]

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

[@venkatesh3439]

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

[@gustavobertolino400]

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

[@kalaimanigovindasamy2205]

Very nice explanation sir about sorting

[@ngozik-opara4373]

This is cool, you are a great teacher.

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

[@shawonsarker4384]

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

[@mithunshaha4342]

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

[@lokeshaggarwal5129]

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

[@mohammedzeeshan146]

Lucid explanation . Awesome work guyz.

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

[@shashankpathak63]

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

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

[@ubernerrd]

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

[@VivekSharma-bl7ul]

wonderful sir , i am really impress your teaching method

[@azimroydar1083]

Your videos are very clear and helpful.thanks alot

[@giorgi23]

Your explanation is really helpful. Good job!!!

[@watchdennyplay21314]

You are awesome dude! Keep being so.

[@rafaelfonseca7942]

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

[@fengqichen8432]

thank you for your intuitive explanation, sir.

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

[@GYANESHWAR27]

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

[@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; } }

[@prestonip]

This video is so good it made me cry

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

[@Code-fr8qx]

The second I saw A[hole] in the video I paused and went straight to the comment section. Not disappointed.

[@beautifullifejourney28liza]

Very nice explanations...thank you so much

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

[@adarshnathaniel8520]

Great Explanation. Understood the concept well XP

[@manishmamgain9697]

Very well explained👍👍

[@shivamgohel8400]

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

[@lakshminarasimmanv]

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

[@jaidheersirigineedi8110]

Keeping all the "A[hole]" comments aside, He explained the algorithm way better than my DS lecturer. Thanks for saving me.

[@muhammadarslanbhatti2139]

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

[@manishrawat4161]

wow , love the way u explain

[@kautukraj]

Very helpful.

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

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

[@md.arifulislam4311]

Superb lecture , carry on dear

[@RonilMalvania]

Very well explained videos. Thanks

[@nknnithinabc]

Best explanation,ever

[@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); } } }