What I want to do in this video is go over what I think is one of the more intuitive ways to sort a list. It's how I would probably sort it, if I had to do it manually. But I want to make it clear, it is not the most efficient way to sort a list. I think it's a good starting point to getting warmed up with sorting lists. It's called insertion_sort. And I'm going to give a graphical description of the algorithm for insertion_sort. And just so you know what, algorithm sounds like a very fancy word, but an algorithm is really just a way of sorting it, or a process for doing it, or a method for doing it. A program is a specific implementation of an algorithm, or it can be a specific implementation of an algorithm. Once I have a general algorithm, I could implement it in Python. I could implement it in C. I could implement it in Java. Those are specific programs. But they'd all be implementing the same way of doing the sort. And that's what I'm describing here, the insertion_sort algorithm. So let's just start with a simple example. Let's say that I have a list. Let's say I have a Python list, because we're going to be working in Python for this. And that list is, let's say, it is 7, 3, 1, 2, 4, 6. And so the way that we do insertion_sort is you go element by element. And then you compare it to the elements before it. And then you look for the first element before it that it is actually less than. And then you just stick it right over there. So let me show you what I'm talking about. So you could start with the 7, the 0-th element over here. But when you start with a 0-th element, you're like, hey, wait, there's nothing before it to compare it to. So it really doesn't make sense to start with the 0-th element. So really, if you were to implement this algorithm, you'll start it with the third element. Or sorry, you'll start it with-- if this is the 0-th element, you'd start it with the first element right over here. If this is 0-th, this is first. I know this can be a little confusing when you refer to this as the first element. But this one's the 0-th. So you start with this 3 here. And then you start comparing it to all of the elements before it. And as soon as you find an element that 3 is less than, you stick it in that part of the list. So what you do is you say, OK, is 3 less than 7? Well, yeah, it is less than 7. So what you want to do is you want to shift 7 where the 3 is. So let me put it out here. So we're trying to compare 3 to everything before it right now. So you say, OK, is 3 less than 7? Yeah, it is less than 7. So let's put the 7 where the 3 is. And let's put the 3 where the 7 is, especially because there's nothing left to compare the 3 to. There's no elements before the 0-th element, so let's just stick the 3 right over there. And so our list now looks like this. Our list now looks like 3, 7, 1, 2, 4, and 6. And one thing you'll find interesting, or something to pay attention to, is as we build this list-- so the 0-th element is now definitely less than the first element. And everything up to and including the first element is now sorted. And that will be true, as we keep going through this. As we keep going through higher and higher indexes, up to and including that index after we've done that pass will be sorted. And I'll try to point that out as we go along. So we did the first index. So we already did the first index. Now we can move on to the second element, which is this 1 over here. And so you take that 1. I'll put it on the side right over here. You take that 1 and you compare it to each of the elements before it. OK, is 1 less than 7? Sure, 1 is less than 7. So let's stick the 7 where the 1 is. And then you could just keep comparing, or you could just stick the 1 where the 7 is. And then you would say, OK, is 1 less than 3? Well, yeah, sure. It's less than 3. So let's stick the 3 where the 1 is. And let's put the 1 where the 3 is. So what is our list now? Our list now is going to look like 1, 1, 3, 7, 2, 4, 6. So notice, after we've gotten to the n-th index-- so in this case, this was the index of 2 where that 1 was right over there-- everything up to and including that index is sorted. This part right here is sorted. Other things are going to be thrown in here, probably, as we go on. But so far, this part is sorted. So you can see by the time we get to the end of this list, everything is going to be sorted. So let's now go to the next index, or the next item in the list. And that is this 2 over here. And so we compare the 2 to the 7. 2 is definitely less than the 7, so let's put the 7 where the 2 is, and let's put the 2 where the 7 is. Now you compare the 2 to the 3. 2 is less than 3. So let's put the 3 where the 2 is, and let's put the 2 where the 3 is. Then compare 2 to 1. Is 2 less than 1? No, it is not less than 1, so we don't have to do anything else. We don't have to keep going to the left. And so now, after this pass-- in this pass, we were comparing this 2 item to everything before that. So after this pass, our list looks like this. Our list looks like 1, 2, 3, 7, 4, 6. And notice everything up to and including the third item, so 0-th 1 2, third item, is now sorted. And now we're ready to look at the next element in the list. And one thing I want to make clear, when you actually implement it, there's a couple of ways to do it. So in this example, we said, hey, 2 is less than 7. We had the 7 replace where the 2 is, which you should do. And then we had the 2 replace where the 7 is. But the reality is you can keep going down, until you find a good place to put the 2, and shifting everything to the right as you do it, and then putting the 2 in. Although this way, it's a little bit easier to keep track of. And well, maybe we'll explore different ways to do it when we actually implement the algorithm. Anyway, let's look at this 4. Same exact idea. 4 is less than 7, so let's put the 7 where the 4 is and put the 4 where the 7 is. Is 4 less than 3? No, it's not less than 3, so we stop. We're done. Now everything up to and including the fourth item in this list, 0, 1, 2, 3, 4, is now sorted. And now our list looks like-- let me scroll down a little bit-- now our list looks like this. Let me write it down. It is 1, 2, 3, 4, 7, and then 6. And now we can go to this last element in the list. This is the 6 that we're now comparing. Actually, the last time we did this, it was a 4 that we cared about. But now we care about the 6. Is 6 less than 7? Sure, it is. So let's put 7 where the 6 is. Let's put a 6 where the 7 is. Is 6 less than 4? No, it's not. And so we stop, because we know that this is going to be sorted. If we went any further, we're just going to get elements that are less than or equal to 4. So we are done. We have sorted this list. The sorted list is now 1, 2, 3, 4, 6, and 7. In the next video, I'm actually going to try to implement this algorithm that I just described. And I'm going to implement it in a simple Python function.
Insertion Sort Algorithm - Algorithms, Mathematics for 2023 is part of preparation. The notes and questions for Insertion Sort Algorithm - Algorithms, Mathematics have been
prepared according to the exam syllabus. Information about Insertion Sort Algorithm - Algorithms, Mathematics covers all important topics for
2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Insertion Sort Algorithm - Algorithms, Mathematics.
Introduction of Insertion Sort Algorithm - Algorithms, Mathematics in English is available as part of our for & Insertion Sort Algorithm - Algorithms, Mathematics in Hindi
Download more important topics related with notes, lectures and mock test series for Exam by signing up for free.
Video Lecture & Questions for Insertion Sort Algorithm - Algorithms, Mathematics Video Lecture full syllabus preparation | Free video exam.
Information about Insertion Sort Algorithm - Algorithms, Mathematics
Here you can find the meaning of Insertion Sort Algorithm - Algorithms, Mathematics defined & explained in the simplest way possible. Besides explaining types of
Insertion Sort Algorithm - Algorithms, Mathematics theory, EduRev gives you an ample number of questions to practice Insertion Sort Algorithm - Algorithms, Mathematics tests, examples and also practice
Insertion Sort Algorithm - Algorithms, Mathematics is the part of for 2023 exam preparation. The content of Insertion Sort Algorithm - Algorithms, Mathematics has been
prepared for learning according to the exam syllabus. Insertion Sort Algorithm - Algorithms, Mathematics covers all important topics for
2023 Exam. Find important questions, notes, tests & features of Insertion Sort Algorithm - Algorithms, Mathematics here.
How EduRev helps you in preparation?
EduRev provides you with complete coverage and for 2023 Insertion Sort Algorithm - Algorithms, Mathematics as a part of our plan for
syllabus to prepare for exam. Our subject experts have curated special courses, tests & mock test
series. All previous year questions (PYQs) & topic wise tests like tests for Insertion Sort Algorithm - Algorithms, Mathematics are provided with detailed
solutions. Download more important topics, notes, lectures and mock test series for Exam by signing up for free.
Download free EduRev App
Track your progress, build streaks, highlight & save important lessons and more!