Insertion Sort Algorithm Made Simple [Sorting Algorithms]

Learn to implement the Insertion Sort algorithm and ace your coding interview.

CONNECT WITH ME

Data Structures and Algorithms is an essential topic taught to computer science and software engineering students to help them learn logical thinking and problem solving. That's why a lot of companies these days ask data structure and algorithm questions in their interviews. Sorting algorithms are particularly important. Even though you never have to implement a sorting algorithm in real life, studying and understanding these algorithms help you become better solving larger, more complex problems.

[lucianboboc]

I have completed all 3 parts, the course is great, i highly recommend it.
A dynamic programming and system design would be a great addition to the existing 3 parts.

[piyushborse]

Now I can say one thing to CS students... ODIN is with us ❤️

[MichaelAdadey]

Mosh has gotta be a really rich guy, because man this guy knows so much

[IoniB]

This made little sense until I realised I was thinking about it wrong. It wasn't until I sat down on my ipad and tried to draw each step that I realised that firstly you are setting the current to the 2nd item in the list and J to just A NUMBER that is 1 less than the index. Then I realised that j-- was setting j to -1 and not 0. And once you do j + 1 = current this is the same as array[0] = current.
So I basically understood it like that: first steps:
array[1] = array[0]
j = -1;
arr[0] = current (array[1])

I don't know if this makes sense to anyone else rn but if you are confused I suggest you just spend some time on it and draw it out at each step. I love Mosh though. He's the only one that actually encourages me to sit down and try something and this makes a huge difference. He breaks the developer's mindset of just watching tutorials forever and not actually practising it. In the last 2 days this is the second sort that he helped me truly understand and implement rather than think that I understand and then when I need to do it I don't actually get it. Awesome work!

[_stack]

You're an inspiration Mosh! so much so that we decided to create a coding channel ourselves. Of course, we are nowhere near your way of teaching, but we see you as an inspiration and a guide for succeeding!

[zivv]

The explanation was very good, the call to action to try it ourselves for 20 minutes is refreshing and wonderful, and when you demonstrated how you actually write the code - it was very informative and clear. Excellent video, thank you!

[mrbbayat]

Well explained, very similar to this book
"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms - The MIT Press (2022)"

[snehanangunoori]

Hi Mosh! Just wanted to say that I especially like how you gave us 20 minutes to attempt the implementation instead of us just directly copying your code. I followed your instructions and was able to implement it by myself! It really made my day (the little things in life)...thank you so much!! I truly enjoy learning from your videos...thanks again! :)

[__nitinkumar__]

This one is for all all my friends who love for loops.

The Approach I took is of swap. Basically I think of it as a swap operation only and not as shift operation, as mentioned by Mosh.
So swap until you find the correct spot for the current element in the sorted portion.
Because of swapping the index of current gets changed, so keeping track of it, and decrementing it after every swap.

private static void insertionSort(int[] arr) {

for (int i = 1; i < arr.length; i++) {
int curr = arr[i];
int currIndex = i;
for (int j = i - 1; j >= 0; j--) {
if (curr < arr[j])
swap(arr, j, currIndex--);
// after swapping the index of curr changes so decrementing
else
break;
// reduce iterations as elements before ith index are sorted
}
}
}

private static void swap(int[] arr, int j, int i) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}

[JasmineWuRealEstate]

Yesss! 👍👍 Why didn't I have this 2 years ago when I was struggling through data structures and algorithms? 😩

[ZBadri]

I just want to say you:
Thanks alot
although its my weekness, l would say l actually like you be my teacher .
If l lived in your city l have found you to be my private teacher.
Despite some web s that you recommend are not responsible in my country, l keep trying to learn .

At least l could say you are so generous , so l wish a happy life for you.

[masonbrown]

The elements are not sorted right after they are moved I thought. Not until the very end are they sorted. That’s what my teacher said and it seems right. Now I’m confused

[heefbrz]

this is explained better than it was to me in school today

[MuhammadIshmaell]

Great explanation, but can any please explain why we're decrementing the value of j in the while loop?

[robloxprisoners]

Mosh please i want your django course cuz your explanation is easy and simple at the same time which motivates more to code even more.PLEASE.PLEASE

[jaygarzon]

What is the purpose of dicrementing the loop variable inside the while loop? Thank you and I hope you all are doing great

[aneeshkatkam]

mosh thank you thank you thank you for these courses

[chirilcugureanu]

I already took your Algorithms course in Java but implemented the algorithms in JavaScript! An amazing course! Really recommend it!

[abhishekshah]

I need the intro music. It's so good <3

[bishowpandey]

Hey mosh you are really a very good teacher. I love your videos. I had learned python by watching your videos. Thank you for all your videos. I have a small request, can you make videos on game development with python. It will be very helpful. Thank you!❤️❤️