- 00:00:00 hi guys in this video we will be going
- 00:00:03 over another basic sorting algorithm
- 00:00:04 bubble sort and we'll be looking at its
- 00:00:07 run time and then at the end I'll go
- 00:00:09 through some pseudocode to write bubble
- 00:00:11 sort bubble sort is a popular sorting
- 00:00:16 algorithm but it is not one of the most
- 00:00:18 efficient ones it works by going through
- 00:00:21 a series of iterations and on each
- 00:00:24 iteration through an array so in this
- 00:00:26 case we have an array of length six we
- 00:00:33 look at adjacent pairs of elements so
- 00:00:36 I'm going to just label the indexes real
- 00:00:37 quick so on a single iteration we look
- 00:00:42 at all the adjacent pairs of elements so
- 00:00:45 we look at 7 2 3 3 & 4 4 & 2 2 & 6 6 & 1
- 00:00:53 and as we go through and look at these
- 00:00:56 pairs we want to swap them so for the
- 00:01:00 example on this first pair of the 0th
- 00:01:04 index and the first index the 7 & 3
- 00:01:06 values we want to swap those values if
- 00:01:11 they are not in increasing order because
- 00:01:14 our goal is to get it an array that is
- 00:01:16 in increasing order at the end of this
- 00:01:18 so we have 3 & 7 now we look at the next
- 00:01:21 adjacent pair which is the swap 7 in the
- 00:01:26 4 well these are also not an order so
- 00:01:29 we'll swap
- 00:01:40 next we look at the second and third
- 00:01:42 indexes and once again they're not in
- 00:01:45 order so we switch them we continue this
- 00:01:50 process until we're all the way at the
- 00:01:52 dead end of our array and we're at the
- 00:01:55 fourth and fifth index so the last
- 00:01:57 adjacent pair and so finally the last
- 00:02:03 one switch to 7 & 1 I get 1 & 7 so that
- 00:02:10 was a single iteration and if you can
- 00:02:17 tell well
- 00:02:19 this 7 right here it used to be right
- 00:02:23 here at this 0th index so a key thing to
- 00:02:27 remember about bubble sort is that on a
- 00:02:29 single iteration you move the next
- 00:02:33 largest or the largest because we're on
- 00:02:36 the first iteration to the far right of
- 00:02:38 the array so like in this iteration we
- 00:02:41 move to the 7 all the way to the end and
- 00:02:43 the next iteration we only have to look
- 00:02:46 at the first 4 or 5 indexes and move the
- 00:02:52 next largest into this fourth spot right
- 00:02:55 here so let's go through that real quick
- 00:02:58 so this is the second iteration we're
- 00:03:00 gonna go through right now and we
- 00:03:04 already have as I stated before we
- 00:03:05 already have that 7 in place so we're
- 00:03:07 gonna just look at the 0 through 4
- 00:03:09 indexes so we take a look at 3 & 4 they
- 00:03:12 are in order so we keep them like that
- 00:03:14 next we look at the 4 & 2
- 00:03:17 they're out of order so we swap them now
- 00:03:22 we have 2 & 4 next we look at the second
- 00:03:26 and third index is the 4 & 6 they're in
- 00:03:28 order so we're good
- 00:03:29 we look at the 6 in the 1 and they are
- 00:03:33 out of order so we want to swap them so
- 00:03:38 we now have 1 & 6 here well we got the 6
- 00:03:41 where we wanted it so we can continue
- 00:03:43 this process
- 00:04:07 so for the sake of time I'm going to go
- 00:04:08 really quickly through the next few
- 00:04:12 iterations so this is the third well
- 00:04:18 swap these in order in order the next
- 00:04:24 pair would swap is the one in the four
- 00:04:28 so you get two three one four this is
- 00:04:32 the third iteration and now this is the
- 00:04:35 third largest element in that spot let's
- 00:04:38 move on to the fourth iteration well two
- 00:04:45 and three already good the one and three
- 00:04:48 they'll have to change so we have one
- 00:04:49 three and look that three is good it's
- 00:04:52 in sorted order the fifth iteration is
- 00:04:56 just this these two elements the two and
- 00:04:59 the one so once we swap them we have our
- 00:05:06 elements in sorted order so for the run
- 00:05:10 time let's imagine instead of having
- 00:05:12 this length six array we have an
- 00:05:15 arbitrarily long length n array so I'm
- 00:05:19 just gonna change this up a little bit
- 00:05:22 so this would be the N minus first
- 00:05:24 position and this is the nth position
- 00:05:25 and we'll just denote the rest by these
- 00:05:28 dots well let's think about how this
- 00:05:31 algorithm worked well we looked at
- 00:05:34 adjacent pairs on each iteration so as
- 00:05:40 you can see I'm working my way from the
- 00:05:42 left of the list to the right of the
- 00:05:46 list and I'm looking at two values each
- 00:05:50 time so I think we can say that this is
- 00:05:53 order n so we look at order n adjacent
- 00:05:57 pairs next we need to figure out how

- 00:06:01 many iterations we have to do to get our
- 00:06:05 list completely sorted so let me real
- 00:06:08 quick change up the array that I have
- 00:06:11 here and put it back so that we have you
- 00:06:16 know seven here six here maybe and then
- 00:06:20 well the key thing to know about when
- 00:06:22 you're counting the iterations is that
- 00:06:24 while this seven might move to the end
- 00:06:26 of the array right here and be the last
- 00:06:29 element the smallest element which in
- 00:06:32 this case we're going to say is one only
- 00:06:35 moves a single position on each
- 00:06:38 iteration so because we have a single
- 00:06:42 move back per iteration in the worst
- 00:06:52 case we're gonna have to do as many
- 00:06:55 iterations as there are like numbers in
- 00:06:59 our array I really will have to do one
- 00:07:01 last but we're gonna have to do the
- 00:07:03 number of swap back Center a shion's on
- 00:07:05 the order of N so on the order of n
- 00:07:09 iterations so this is the adjacent pairs
- 00:07:13 we look at on a single iteration and
- 00:07:18 that's order of N and now we just said
- 00:07:20 that number of iterations we have is
- 00:07:23 order n so that gives us a runtime of oh
- 00:07:28 of N squared so this is the runtime we
- 00:07:36 also can really quick to the space
- 00:07:38 requirement the space complexity and
- 00:07:40 well that's pretty simple we didn't need
- 00:07:44 any extra space to do this we just
- 00:07:46 swapped elements we just swapped
- 00:07:47 adjacent pairs of elements so all we
- 00:07:50 need is the list itself so all we need
- 00:07:53 is just this list sorry that it's
- 00:07:55 getting a little bit C so that is order
- 00:07:57 n we will finish this video by going
- 00:08:02 through the pseudocode for bubble sort
- 00:08:05 so we'll begin by defining our function
- 00:08:11 so do definition of bubble sort and
- 00:08:14 we'll have this function take in a list
- 00:08:17 of numbers and we'll just call that
- 00:08:19 numbs foreshorten next we're going to
- 00:08:23 just define a variable called n which is
- 00:08:25 just going to be the length of the
- 00:08:26 numbers and we'll find this useful when
- 00:08:28 we're iterating through the array
- 00:08:32 next we will need a for loop which
- 00:08:35 iterates that represents the number of
- 00:08:38 iterations that we will need in the
- 00:08:40 worst case scenario
- 00:08:41 so we'll do range and after this we will
- 00:08:46 have another for loop and this time this
- 00:08:51 for loop is kind of representing the
- 00:08:53 adjacent payers that we'll have to deal
- 00:08:55 with so we'll say that this is in range
- 00:08:58 0 to n minus I minus 1 so I explicitly
- 00:09:06 wrote out this zero right here because I
- 00:09:09 wanted to show that that's the 0th index
- 00:09:10 and then the N minus 1 so that negative
- 00:09:14 1 comes from the fact that the last
- 00:09:17 element we care about is this because if
- 00:09:20 we are looking at adjacent payers in our
- 00:09:23 the rest of our code we'll just have a
- 00:09:24 little mention that we have an N plus 1
- 00:09:27 value right here so we don't want to go
- 00:09:29 beyond our list over here ok and then
- 00:09:34 also the minus I is because on each
- 00:09:37 iteration we put the largest element to
- 00:09:39 the back of the list so that back of the
- 00:09:42 list is sorted after each iteration so
- 00:09:48 we sort we have one more value that is
- 00:09:50 sorted after each iteration ok so the
- 00:09:54 last step is to compare the the adjacent
- 00:09:58 pairs so to compare like the 7 and 6 for
- 00:10:01 example well to do this we'll have an if
- 00:10:04 statement will do if array J tellement
- 00:10:09 so we're looking at the J element right
- 00:10:12 now so any one of those elements so this
- 00:10:14 could be J and if that is greater than
- 00:10:18 array J plus 1 well in this case it is
- 00:10:25 we just want to swap array J and
- 00:10:33 arrey J +1 so in this example seven in
- 00:10:40 the six were in fact in the wrong order
- 00:10:44 so we would swap it up so we'd have this
- 00:10:48 V six and then seven and so to kind of
- 00:10:52 recap the run time we can say that this
- 00:10:56 swap function is constant of one we have
- 00:11:00 two nested loops loops are gonna be this
- 00:11:04 is on the order of n it's bounded by n
- 00:11:07 because all values are N or less and
- 00:11:09 this is in range this one right here is
- 00:11:14 in range n so this is also of n so if we
- 00:11:17 multiply these things together we get
- 00:11:19 our run time that we expected of oh of N
- 00:11:21 squared thank you for watching this
- 00:11:25 video if you have future video requests
- 00:11:28 in computer science math machine
- 00:11:30 learning etc please send me an email at
- 00:11:33 Keith G learning at gmail.com thank you