Insertion Sort Explained & Pseudocode

00:00:00 hi guys this is Keith galley and in this
00:00:03 video we will be going over one of the
00:00:05 basic sorting algorithms insertion sort
00:00:09 the goal of any sorting algorithm is to
00:00:11 take a list such as 5 2 4 6 1 3 and put
00:00:16 it in increasing order
00:00:18 insertion sort does this by going
00:00:21 through a series of iterations on each
00:00:24 iteration we take a bigger and bigger
00:00:27 sub list and make sure that is sorted by
00:00:29 swapping back any value that is not in
00:00:33 place so on the first iteration we look
00:00:37 at just 5 that's just a single number so
00:00:40 it's sorted next we look at 5 & 2 2 is
00:00:45 comes before or 5 so we would swap that
00:00:47 2 back now we would have a sorted to 5
00:00:50 and we look at 4 so if this was to 5 for
00:00:55 now well the 4 would need to be swapped
00:00:58 in between the 2 and the 5 I'll write
00:01:03 this out a little bit more explicitly so
00:01:07 on the first iteration we just look at 5
00:01:13 and 5 is a single number so it's sorted
00:01:16 second iteration we look at 5 and 2 well
00:01:22 2 becomes before 5 so we should swap the
00:01:26 order of these two things to become 2 5
00:01:32 all right now let's go to the third
00:01:35 iteration so we have the list 2 5 4 here
00:01:38 and we're on iteration 3 so in this case
00:01:46 we have we're looking at the sub list 2
00:01:49 5 4 and only because the first two
00:01:53 already sorted we're just gonna have to
00:01:54 figure out how many times to swap back
00:01:56 for well 4 is larger than 2 and smaller
00:02:00 than 5 so we can either swap it right
00:02:03 back one time so it just takes the place
00:02:06 of the 5 so it goes to 4
00:02:10 and we'll put this in our manor right
00:02:14 here
00:02:15 alright and this process just keeps
00:02:17 repeating so now we would look at 6 on
00:02:19 iteration 4
00:02:21 well 6 is bigger than 5 so it's in the
00:02:26 correct spot so 2 foot so 2 4 5 6
00:02:34 nothing changes so now let's look at
00:02:37 this one this one is smaller than
00:02:39 anything we've seen before and we have
00:02:42 our first four numbers already sorted so
00:02:44 we have 2 4 5 6 1 well you're gonna have
00:02:49 to swap this then we're gonna have to
00:02:52 swap again then we're gonna have to swap
00:02:55 again and then we're gonna have to swap
00:02:57 again so we ran out to do four swaps so
00:02:59 we keep swapping this back until we find
00:03:01 a number that is smaller than 1 or if
00:03:06 one's the smallest number we just swap
00:03:08 it all the way to the front of the list
00:03:09 so this will become 1 2 4 5 6 all right
00:03:16 so we can update our chart to show this
00:03:23 so we now have 1 2 4 5 6 finally on the
00:03:31 last iteration iteration 6 we are
00:03:36 looking at the whole array so we're
00:03:38 looking at 1 2 4 5 6 3 in this case
00:03:46 we're gonna have to swap the 3 right
00:03:49 here so we're not to swap it one two
00:03:51 three times so 1 2 3 times and get it to
00:03:57 be before this 4
00:04:04 so at the end of that four five six so
00:04:10 after six iterations we have all of our
00:04:13 numbers sorted in increasing order let's
00:04:18 quickly go over the runtime of this
00:04:19 algorithm when the example I showed we
00:04:22 had six numbers in our array and we're
00:04:24 required to go through six iterations of
00:04:26 the algorithm that's imagine we didn't
00:04:29 just have six but we had an arbitrarily
00:04:31 long array and that's called this size
00:04:35 of this array and so we know we would
00:04:40 need oh of n iterations to get through
00:04:42 this algorithm and then to complete a
00:04:46 runtime analysis we need to count how
00:04:49 many times we had to swap back numbers
00:04:51 well in the worst case we would have a
00:04:58 array that is sorted in decreasing order
00:05:02 so in each each time we see a new number
00:05:05 we'd have to swap it back to the front
00:05:08 of the list so in this last number we'd
00:05:14 have to swap it all the way back down
00:05:16 the line so n times so we know that the
00:05:20 maximum amount of swaps is n so we can
00:05:24 bound everything on the swap hand by n
00:05:28 so we have an O of n times o of n so
00:05:31 this gives us a total runtime of oh of N
00:05:34 squared the space requirements for this
00:05:39 algorithm we don't need any extra space
00:05:41 we maybe just need a couple temporary
00:05:43 variables but we can bound the space by
00:05:46 oh of n we'll finish this video by
00:05:50 quickly going through the pseudocode for
00:05:52 insertion sort so let's begin by

00:05:54 defining our function insertion sort
00:06:01 and insertion sort is going to take in a
00:06:04 list of numbers and we'll just call
00:06:06 these numbs for short so the goal of
00:06:08 this algorithm is to return this list
00:06:11 nums in sorted order so we'll begin by
00:06:14 iterating through the N values we have
00:06:19 in our array so to do this we'd go for I
00:06:25 in range 1 to the length of the numbers
00:06:35 so that gives us the end value that
00:06:38 we're looking for we're gonna want to do
00:06:41 we're gonna want to swap back and so we
00:06:44 start at 1 here so this is 1 we start at
00:06:47 1 right here because we never need to
00:06:50 slowly just look at this 6 because it's
00:06:53 already sorted we're gonna have to look
00:06:55 at these first two numbers though so
00:06:57 we'll start right here and just figure
00:06:59 out if we need to swap that before the 6
00:07:01 or not all right
00:07:05 so once we do that I'm going to just
00:07:07 have a variable that I define as current
00:07:10 value and that will start off by being
00:07:13 just the value at the index in numbers
00:07:18 so nums I thinned X it'll also have a
00:07:23 position variable and that will just be
00:07:27 I so now we want to swap back so if we
00:07:34 said we're at this 4 right here we'd
00:07:36 want to swap it back until it is in the
00:07:41 correct position in the array so how do
00:07:45 we do that in code so what we can do is
00:07:48 while position is greater than 0 so
00:07:53 basically just meaning that we don't
00:07:56 need to swap back once we're here we're
00:07:58 here you know it's already at the first
00:08:00 spot so it's in sorted order sorted
00:08:03 order it's the smallest value so we'll
00:08:05 end right here while position is greater
00:08:07 than 0 and the value right before it so
00:08:14 numb
00:08:16 position minus one is greater than the
00:08:22 current value we want to swap it back so
00:08:31 what we can do to swap it back is we can
00:08:34 just say numbs position is equal to
00:08:41 numbs position minus one and then we
00:08:50 just want to decrease our position
00:08:53 pointer so that if we need to swap back
00:08:55 again we're swapping back from the
00:08:58 correct spot so position equals position
00:09:03 minus one then finally we want to update
00:09:11 our current value to be in the final
00:09:13 resting spot so that will be numbs is
00:09:17 outside the wild loop because we're done
00:09:19 swapping numbs position equals the
00:09:25 current value okay so just to go over
00:09:27 the pseudocode and look at one duration
00:09:29 let's imagine that we were at index
00:09:32 value index value of three so we get the
00:09:39 current value at position 3 which is two
00:09:43 and we're just storing position in I or
00:09:48 as I so three so I is equal to three Oh
00:09:52 so while position is greater than zero
00:09:55 and the numbers of position minus 1 is
00:09:58 greater than current value so position
00:10:01 minus one is three minus one so that
00:10:04 equals two so that value there is four
00:10:07 and that is greater than our current
00:10:10 value of two so we would swap those two
00:10:13 values so you'd go we would change it so
00:10:18 it's two and then four and then we check
00:10:22 again to see if 3 is greater than 2
00:10:27 which it is
00:10:28 so then we after we've decriminalization
00:10:34 – or prison 1 versus position – and see
00:10:39 that that they get swapped so we've kind
00:10:49 of end with 3 here and then finally
00:10:53 numbers a position so because we're D
00:10:57 commenting this each time we get a final
00:11:01 position of one so this is a 0th index
00:11:05 and this is the first index and we get
00:11:08 we just put our current value there so
00:11:09 we get 1 2 3 4 5 6 and it works cool
00:11:13 thank you for watching this video if you
00:11:16 have recommendations for future videos
00:11:18 let me know

You may also like