Insertion Sort - Data Structures & Algorithms Tutorial Python #16

Key Takeaways

we are discussing insertion sort in this video as usual we'll cover some theory then we'll implement insertion short in python at the end we have an interesting exercise for you to solve so make sure you watch the land let's say you have this unsorted list of numbers one way you can sort these numbers is create a different array on the left hand side let's say that is your sorted array pick the first element from the unsorted array put it in the sorted array in such a way that that array remains sorted right now there are no elements we can just put the element directly there let's take the second element 38 you want to put in that array so that that array remains sorted so you will put 38 after 21 then you pick 29 now when you put 29 into that array you cannot put it at the end because it has to be after 29 before 38 so you'll have to do little bit or a shuffling here and then insert it in the middle so you're moving 38 uh one element behind next comes 17 for 17 you will put that into the first place so you take 17 from unsorted array compare it with the elements starting from beginning in the sorted array when you compare it with 21 you find that 21 is already greater so then you just put it in the front so you continue this way and on the left hand side you will get a sorted array this approach is fine but it requires using separate array the question is can you do it without using a separate array so just pause the video think about this i think there is a way you can you use it uh you can do this from the same or itself so that you don't have to create an extra array all right let's talk about that approach i hope during that pause you get an idea see the way you learn algorithms is before looking at the solution directly you try to come up with your own idea on how you can solve a problem that will make you very good programmer that will make your algorithms skills very very strong so now i have this array so i take a pointer i start from the second element so anything to the left hand side of the pointer is a sorted array when i start with second element the first element is of course assorted because if you have one element array it is sorted all the time now you take the second element and you try to put in on the left hand side so that it is sorted so left hand side it's 21 which is less so already sorted so let's move the pointer okay when you move the pointer i am changing the color of this 38 cell which means now the first two elements are sorted i go to 29 now i compare it with the sorted array so that then i go to 38 first then 38 is bigger okay so then i go to 21 21 is smaller which means i need to insert 29 in between 20 1 and 38 so i will do that and we'll look into python code how exactly to do this uh but in this theory part just assume that you're picking up element from unsorted array putting it in a sorted array so that the order is maintained you move to 17 then you look at the left hand side so you begin with 38 first 38 is bigger okay you move to 29 bigger move to 21 bigger you insert 17 at the beginning so this is how now this looks and you keep on doing this until your entire array is sorted so you see how a simple trick can kill so many birds in one stone alright let's talk about the performance i took this from wikipedia the worst case performance is order of n square comparison and swaps so just imagine the whole array is not sorted so every time you pick up the element you have to perform those many swaps so you are going through an element and for every element you are doing n swaps that's why order of n square base case is order of n because even if the array is sorted you're still doing n comparison and swaps will be order of one the space complexity there's not much space complexity maximum order of one because you might create one variable to hold that anchor element all right again this is from wikipedia it's a simple algorithm you will see in python it's only few line of code but when your list is very big it is not efficient so you will use this for maybe smaller list and here are some of the benefits you can read through them benefits and some of the aspects of insertion sort when you use sort function in python it already uses some internal uh sum algorithm so you will never have to move in most of the cases when you're doing python programming you don't have to do insertion sort implementation on your own you're using this in build algorithm but having this understanding of how algorithm works allows you to develop this algorithmic mindset and you might use the things which you learn from this to make your code better let's jump into coding now as you saw in the presentation we always start with the first element so we'll run a loop where we'll say for i in range one two length of elements okay do something we saw that the first element you can consider it as sorted then start with the second element and then uh try to take one element at a time and try to put it in the sorted area on the left hand side in a right order so we'll call the element that we are dealing with right now and anchor so your anchor is elements of i and what you're doing is you're going on the left hand side so left hand side is what left hand side is element which is one place less than the current element so let's call it j j is 1 less than your current element right so i minus 1 and you want to start from that to all the way till 0 so while j is greater than equal to 0 and you want to stop so until so let's do this until your elements of j are greater than anchor you continue but right and then when you continue you want to swap those items so you see this case here here uh so here uh let's see yeah when you're 17 you start with okay let's do this okay when you are 29 you start with 38 38 is greater so you continue you get 21 when you get 21 you stop okay and you make an exchange so and by the way when you're here what you'll do is you store 29 lesson in an anchor and then you swap 38 here okay so literally what you're doing is 29 is here so this is your anchor now okay and then you put 38 here you see you put 38 here then you go to 21 so 21 is greater than this so you stop okay and then what you do is the anchor which is 29 you put here so that's the method so first we are doing swap so in j plus one we are copying element from the left so this is just swapping from left to right of course you need to reduce j and then in the end you will do j plus 1 is equal to anchor so when your loop is terminated you know when you're here at the at the 21 element this will be your j and you will do j plus one which is this and assign anchor so it will be 29. let's run you see the arrow is sorted so only few line of code very simple and i have this habit of running through different scenarios whenever i am writing my code so i will take different arrays one is empty one has one element one is shorted in reverse order and i want to test my code and you will notice in the output that all these arrays are sorted now comes the most interesting part of this tutorial which is an exercise without doing exercises it's impossible to learn data structures and algorithms i have this question here where you have a list of numbers you have to find a running median median is an even number list where median is an average of two middle numbers in a sorted list so when you take this array you will use some in some technique you learned in insertion short to build a sorted array somehow on the go and take a median okay so try it out i hope it works for you do not click on the solution without trying because if you click on solution without trying there are three disadvantages once your computer will get coronavirus second that guest who is very annoying will come to your home and stay for a month and third when you are watching your favorite cricket match uh you will get a power cut in your home so if you don't want to go through this horrible experiences make sure you try on your own first then you click on the solution thank you