1 00:00:06,720 --> 00:00:13,500 In our previous lecture, we got an overview on what bubble sort is and how it works. 2 00:00:13,950 --> 00:00:19,920 So now that we have a good understanding of how Bubbles sort works, we can begin implementing our own 3 00:00:19,920 --> 00:00:22,290 solution for that algorithm. 4 00:00:22,860 --> 00:00:29,940 So the first thing I want to do is create a new function called bubble sort, and it's going to look 5 00:00:29,940 --> 00:00:33,410 very similar to what we did for selection. 6 00:00:33,780 --> 00:00:42,000 So we're going to create a bubble sort function and we're going to pass in a mutable reference to a 7 00:00:42,000 --> 00:00:47,880 vector that's also going to return a vector. 8 00:00:51,470 --> 00:00:55,610 And then down here, I want to go ahead and create some of our test cases. 9 00:00:55,610 --> 00:00:58,190 So we will say let mute vec 10 00:01:01,130 --> 00:01:03,320 equals vec. 11 00:01:03,320 --> 00:01:09,020 And then in here I want to mimic our test cases that we did in the previous lecture. 12 00:01:09,020 --> 00:01:10,310 So we did 13 00:01:10,310 --> 00:01:20,390 a5411132 14 00:01:21,290 --> 00:01:23,180 and then we also did 15 00:01:25,850 --> 00:01:26,750 a. 16 00:01:29,720 --> 00:01:36,620 Five one, four, two and eight. 17 00:01:37,730 --> 00:01:47,450 So now in here, we know that we are going to run bubble sort and we're going to pass in a mutable reference 18 00:01:47,450 --> 00:01:48,470 to our VEC. 19 00:01:49,400 --> 00:01:57,650 And then we know that we're going to want to print it out to make sure that our vector was properly 20 00:01:57,650 --> 00:01:58,370 sorted. 21 00:02:02,880 --> 00:02:04,440 And we'll stop there for now. 22 00:02:04,440 --> 00:02:08,340 That way we can make sure that this at least works before we continue down here. 23 00:02:09,840 --> 00:02:16,170 So now up here in the function, we're going to start implementing in our algorithm so we know that 24 00:02:16,170 --> 00:02:17,580 we're going to need to for loops. 25 00:02:17,580 --> 00:02:27,210 So we'll go ahead and create our first for loop and we'll say four I and one to the array dot length 26 00:02:27,390 --> 00:02:28,500 minus one. 27 00:02:31,530 --> 00:02:38,730 And since we knew we know from the previous lecture that we actually don't use this AI variable, we 28 00:02:38,730 --> 00:02:41,430 can substitute it with the underscore. 29 00:02:41,460 --> 00:02:46,830 And basically this tells our compiler, Hey, we don't care about this value. 30 00:02:47,070 --> 00:02:52,620 So just put a placeholder in there and we're not going to reference that value at all. 31 00:02:53,490 --> 00:02:58,920 But in our next for Loop, we do know that we're going to reference J and and J is going to go from 32 00:02:58,920 --> 00:03:06,540 zero to array length minus two. 33 00:03:07,530 --> 00:03:10,620 And then here is where we are going to do our check. 34 00:03:10,950 --> 00:03:24,060 So we're going to say if array of J is greater than array of J plus one, well, now we want to do our 35 00:03:24,060 --> 00:03:24,630 swap. 36 00:03:24,630 --> 00:03:31,470 So we will say erase swap and we have J and J plus one. 37 00:03:33,270 --> 00:03:40,710 And at the very end we want to return our array and then we will get an error mismatch down here because 38 00:03:40,710 --> 00:03:45,600 it says it expected a stroke of Vec i8 and we found immutable reference. 39 00:03:45,600 --> 00:03:52,410 So we can quickly rectify that by saying two VEC and now our error is gone. 40 00:03:53,550 --> 00:03:59,250 So now if we come back down here and we execute our code, we would expect to see the first vector of 41 00:03:59,250 --> 00:04:05,130 5413 to print out a sorted vector which we see down here. 42 00:04:05,130 --> 00:04:08,970 We see that we have one, two, three, four and five. 43 00:04:08,970 --> 00:04:12,510 So our bubble sort is working correctly. 44 00:04:12,510 --> 00:04:23,040 But to verify, let's run it on our second test case of our VEC two and let's do the same thing where 45 00:04:23,040 --> 00:04:25,560 we just go ahead and print that out. 46 00:04:28,860 --> 00:04:36,930 And if we run this again, we see we have one, two, four, five, eight, print it out, which is 47 00:04:36,930 --> 00:04:41,040 sorted of the vector containing 51428. 48 00:04:41,040 --> 00:04:41,700 So awesome. 49 00:04:41,700 --> 00:04:45,840 So it looks like our bubble sort algorithm is indeed working correctly. 50 00:04:47,010 --> 00:04:53,130 But if you remember from the previous lecture, there are times where our algorithm can be sorted or 51 00:04:53,130 --> 00:05:01,320 excuse me, our vector can be sorted, but we're still executing these codes of these blocks of code. 52 00:05:01,320 --> 00:05:10,410 Therefore we're wasting resources and time because we could still be executing at this loop, even though 53 00:05:10,410 --> 00:05:12,540 we know that we're sorted in here. 54 00:05:13,290 --> 00:05:21,840 So we can actually do a very slight little optimization here and we can create a immutable boolean called 55 00:05:22,290 --> 00:05:25,320 Sorted and we'll go ahead and set it to true. 56 00:05:26,460 --> 00:05:35,760 But we'll also at each new iteration of the loop, we'll make sure that it is set to true because we 57 00:05:35,760 --> 00:05:41,220 know that if this block of code gets executed, then we are not sorted. 58 00:05:41,220 --> 00:05:44,130 So that means we want it to keep sorting out. 59 00:05:44,550 --> 00:05:50,520 But if this block of code never gets executed, then that means we are sorted. 60 00:05:50,850 --> 00:05:59,070 And since we have this boolean here and it won't get updated in here because of it's sorted, this block 61 00:05:59,070 --> 00:06:00,600 of code never gets updated. 62 00:06:00,750 --> 00:06:09,510 Then we can put an if statement down here that says, Hey, if we're sorted then I want you to break 63 00:06:09,510 --> 00:06:13,830 out of this loop, meaning this outer loop. 64 00:06:15,040 --> 00:06:20,950 And so if sorted here, this basically says if sordid is true, then break out. 65 00:06:21,310 --> 00:06:26,950 So with that little bit of optimization, just to make sure our code still functions as desired. 66 00:06:26,950 --> 00:06:30,550 One, two, three, four, five and one, two, four, five and eight. 67 00:06:30,640 --> 00:06:32,620 Those are the correct outputs. 68 00:06:33,640 --> 00:06:43,750 So this is an optimization that would be better for a much larger array that does sort itself, let's 69 00:06:43,750 --> 00:06:49,570 say, halfway through or we just cut the O of in squared in half. 70 00:06:49,810 --> 00:06:57,700 So obviously with certain sizes of arrays, this would be a considerable performance increase. 71 00:06:58,930 --> 00:07:03,970 But that was just something I wanted to point out, just to kind of keep in the back of your mind as 72 00:07:03,970 --> 00:07:09,280 we go through these algorithms, I want you to try to think of ways that maybe you can optimize them. 73 00:07:09,280 --> 00:07:15,880 And if you do have unique solutions to optimize some of these arrays because there's definitely optimizations 74 00:07:15,880 --> 00:07:23,410 to be made, please share them with all with me and the rest of the students in the course. 75 00:07:24,100 --> 00:07:27,310 But hopefully you enjoyed learning about bubble sort. 76 00:07:27,430 --> 00:07:33,100 And we will continue looking at a few more algorithms in the next lecture.