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