Coding

# 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