Coding

# Bubble Sort Explained & Pseudocode

• 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