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