- 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