Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,173 --> 00:00:02,566 (bubbly music) 2 2 00:00:02,566 --> 00:00:05,420 (keys typing) 3 3 00:00:05,420 --> 00:00:06,570 In this video we're going 4 4 00:00:06,570 --> 00:00:08,670 to implement the bubble sort algorithm 5 5 00:00:08,670 --> 00:00:12,430 that we just went through using slides in the last video. 6 6 00:00:12,430 --> 00:00:15,070 So I'm gonna start by creating a new project. 7 7 00:00:15,070 --> 00:00:17,780 Now I'm gonna go through this one more time 8 8 00:00:17,780 --> 00:00:19,360 and then from this point forward, 9 9 00:00:19,360 --> 00:00:21,550 I'm going to assume that you understand 10 10 00:00:21,550 --> 00:00:24,180 how to create a project so when we start a video 11 11 00:00:24,180 --> 00:00:26,910 I'll already have the project created. 12 12 00:00:26,910 --> 00:00:30,430 But, for one last time, we go up to file, 13 13 00:00:30,430 --> 00:00:32,493 new, project, 14 14 00:00:33,910 --> 00:00:35,650 and I want a Java project, 15 15 00:00:35,650 --> 00:00:39,020 so I'll make sure Java is selected on the left-hand side, 16 16 00:00:39,020 --> 00:00:41,710 and we don't need to check any of these boxes. 17 17 00:00:41,710 --> 00:00:45,240 I have my project SVK set to Java nine. 18 18 00:00:45,240 --> 00:00:46,440 I'm going to click next. 19 19 00:00:48,020 --> 00:00:51,410 I want the IDE to create the main method for me, 20 20 00:00:51,410 --> 00:00:53,090 the main class and the main method 21 21 00:00:53,090 --> 00:00:57,150 so I'll select that and click next. 22 22 00:00:57,150 --> 00:00:59,423 And I'm gonna call this project bubble sort. 23 23 00:01:00,550 --> 00:01:03,330 And I'm going to change the package 24 24 00:01:03,330 --> 00:01:08,140 to academy.learnprogramming.bubblesort. 25 25 00:01:09,320 --> 00:01:10,850 And I'm gonna click finish, 26 26 00:01:10,850 --> 00:01:12,710 and because I have a project open, 27 27 00:01:12,710 --> 00:01:14,870 it's asking me if I wanna use the same window 28 28 00:01:14,870 --> 00:01:17,203 and I do, so I'm gonna click this window. 29 29 00:01:19,120 --> 00:01:22,193 And there we go, we have our new project. 30 30 00:01:22,193 --> 00:01:24,650 Fine to move this over a little to make some more room, 31 31 00:01:24,650 --> 00:01:26,343 I'm going to delete this comment. 32 32 00:01:27,450 --> 00:01:29,540 And this is a rather simple algorithm 33 33 00:01:29,540 --> 00:01:31,760 so we're just gonna do the implementation 34 34 00:01:31,760 --> 00:01:33,400 within the main method. 35 35 00:01:33,400 --> 00:01:38,400 Now before we do that, I'm going to write a swap method. 36 36 00:01:38,530 --> 00:01:42,110 As you'll see, a number of the sort algorithms we'll look at 37 37 00:01:42,110 --> 00:01:43,840 swap elements at some point, 38 38 00:01:43,840 --> 00:01:45,190 and that's true of bubble sort. 39 39 00:01:45,190 --> 00:01:48,713 It swaps elements, so I'm going to write a swap method. 40 40 00:01:49,830 --> 00:01:51,630 So I'm gonna say public static, 41 41 00:01:51,630 --> 00:01:53,310 it has to be static because we're going to be 42 42 00:01:53,310 --> 00:01:55,510 calling it from the main method. 43 43 00:01:55,510 --> 00:01:59,700 Void swap, and this method's going to take three parameters, 44 44 00:01:59,700 --> 00:02:03,280 it's going to take the array that we're sorting, 45 45 00:02:03,280 --> 00:02:05,813 and it's going to take two indices. 46 46 00:02:08,241 --> 00:02:10,640 And these two indices are the indices 47 47 00:02:10,640 --> 00:02:12,340 of the elements we want to swap. 48 48 00:02:12,340 --> 00:02:15,490 So if we want it to swap elements three and four, 49 49 00:02:15,490 --> 00:02:17,610 we pass the array in, and we pass 50 50 00:02:17,610 --> 00:02:20,193 three for I, and four for J. 51 51 00:02:21,410 --> 00:02:23,210 So the first thing we're gonna do in this method 52 52 00:02:23,210 --> 00:02:25,530 is check whether I equals J. 53 53 00:02:25,530 --> 00:02:28,450 Because if I equals J, there's nothing for us to do. 54 54 00:02:28,450 --> 00:02:32,003 So I'll say if I, I equals J, 55 55 00:02:32,970 --> 00:02:34,053 we'll just return. 56 56 00:02:35,070 --> 00:02:37,010 Because essentially if I equals J 57 57 00:02:37,010 --> 00:02:40,580 we're saying we wanna swap element two with element two 58 58 00:02:40,580 --> 00:02:42,960 or swap element three with element three, 59 59 00:02:42,960 --> 00:02:44,350 so there's nothing for us to do. 60 60 00:02:44,350 --> 00:02:46,330 There's actually no element to swap. 61 61 00:02:46,330 --> 00:02:48,790 But if I isn't equal to J, then we do 62 62 00:02:48,790 --> 00:02:52,110 have elements to swap and so what we're going to do 63 63 00:02:52,110 --> 00:02:54,840 is we're going to create a temporary int variable 64 64 00:02:54,840 --> 00:02:57,860 and we're going to say array I 65 65 00:02:59,160 --> 00:03:00,980 into that variable. 66 66 00:03:00,980 --> 00:03:04,550 So temp will now contain the value at array I. 67 67 00:03:04,550 --> 00:03:06,660 And then we're going to assign the value 68 68 00:03:06,660 --> 00:03:09,453 at array J to array I. 69 69 00:03:12,110 --> 00:03:14,313 Equals array J. 70 70 00:03:15,230 --> 00:03:16,950 Now it's okay for us to do this. 71 71 00:03:16,950 --> 00:03:20,010 We've overwritten the value that was at array I, 72 72 00:03:20,010 --> 00:03:22,750 but that's fine because we've saved it in temp. 73 73 00:03:22,750 --> 00:03:24,790 And so the final thing we have to do 74 74 00:03:24,790 --> 00:03:28,030 is assign temp to array J. 75 75 00:03:28,030 --> 00:03:31,740 So we'll say array J equals temp. 76 76 00:03:31,740 --> 00:03:34,210 So we assign what's at I to temp, 77 77 00:03:34,210 --> 00:03:36,270 we assign what's at J to I, 78 78 00:03:36,270 --> 00:03:38,300 and then we assign what's at temp to J. 79 79 00:03:38,300 --> 00:03:40,290 So, when we exit this method, 80 80 00:03:40,290 --> 00:03:44,190 what used to be at position J will now be at position I, 81 81 00:03:44,190 --> 00:03:47,780 and what used to be at position I will now be at position J. 82 82 00:03:47,780 --> 00:03:49,560 Alright, so now that we have a swap method, 83 83 00:03:49,560 --> 00:03:51,200 let's create our intArray. 84 84 00:03:51,200 --> 00:03:54,720 So I'll say int, intArray equals, 85 85 00:03:54,720 --> 00:03:57,310 and we'll use the same values we used on the slide, 86 86 00:03:57,310 --> 00:04:01,273 20, 35, -15, 7, 87 87 00:04:02,490 --> 00:04:06,013 55, 1, and -22. 88 88 00:04:08,180 --> 00:04:11,470 And now we wanna use the bubble sort algorithm 89 89 00:04:11,470 --> 00:04:13,010 to sort this array. 90 90 00:04:13,010 --> 00:04:14,840 Now, the implementation that I'm going 91 91 00:04:14,840 --> 00:04:17,040 to show you is one implementation. 92 92 00:04:17,040 --> 00:04:19,970 There are other implementations of this algorithm, 93 93 00:04:19,970 --> 00:04:21,640 there'll be a different implementation 94 94 00:04:21,640 --> 00:04:23,900 to sort in descending order. 95 95 00:04:23,900 --> 00:04:26,450 Some of the implementations expand 96 96 00:04:26,450 --> 00:04:29,210 the sorted partition from left to right 97 97 00:04:29,210 --> 00:04:30,740 rather than from right to left. 98 98 00:04:30,740 --> 00:04:33,810 I'm going to implement what I showed you in the slides. 99 99 00:04:33,810 --> 00:04:36,570 And so we're going to say for int, 100 100 00:04:36,570 --> 00:04:39,630 last unsorted index 101 101 00:04:39,630 --> 00:04:43,360 equals array.length 102 102 00:04:43,360 --> 00:04:46,273 minus one, that should be intArray actually. 103 103 00:04:47,590 --> 00:04:50,730 So remember that at the beginning of the algorithm, 104 104 00:04:50,730 --> 00:04:55,280 the entire array is unsorted, and so the last unsorted 105 105 00:04:55,280 --> 00:04:58,440 index will be the last valid index in the array, 106 106 00:04:58,440 --> 00:05:00,660 and that's intArray.length minus one. 107 107 00:05:00,660 --> 00:05:03,480 So that's what we're initialising that to. 108 108 00:05:03,480 --> 00:05:06,120 And then we're going to do this as long 109 109 00:05:06,120 --> 00:05:10,040 as the last unsorted index is greater than zero and 110 110 00:05:11,740 --> 00:05:13,650 after each iteration we're going to 111 111 00:05:13,650 --> 00:05:16,910 decrement the last unsorted index. 112 112 00:05:16,910 --> 00:05:19,440 Now remember that because we're bubbling 113 113 00:05:19,440 --> 00:05:22,180 large values to the end of the array, 114 114 00:05:22,180 --> 00:05:26,270 the sorted partition is growing from right to left. 115 115 00:05:26,270 --> 00:05:30,360 And so the last unsorted index starts at six 116 116 00:05:30,360 --> 00:05:32,820 and after the first iteration it's now 117 117 00:05:32,820 --> 00:05:35,080 going to be five because whatever's here 118 118 00:05:35,080 --> 00:05:37,250 will be in the sorted partition. 119 119 00:05:37,250 --> 00:05:39,850 And then after the second iteration it'll be four, 120 120 00:05:39,850 --> 00:05:42,220 because then these two elements will be sorted. 121 121 00:05:42,220 --> 00:05:44,190 And three, two, et cetera. 122 122 00:05:44,190 --> 00:05:48,600 And so the index is going to go from six to zero, 123 123 00:05:48,600 --> 00:05:50,810 and once we hit zero, we can stop. 124 124 00:05:50,810 --> 00:05:54,080 Because at that point, the entire array is sorted. 125 125 00:05:54,080 --> 00:05:56,040 So that's the outer loop. 126 126 00:05:56,040 --> 00:05:58,180 For each iteration of the outer loop, 127 127 00:05:58,180 --> 00:06:00,230 we want to traverse the array. 128 128 00:06:00,230 --> 00:06:05,180 And we want to bubble the largest value that's unsorted 129 129 00:06:05,180 --> 00:06:07,010 into the sorted partition. 130 130 00:06:07,010 --> 00:06:09,330 So we want to bubble the largest value 131 131 00:06:09,330 --> 00:06:10,370 to the end of the array. 132 132 00:06:10,370 --> 00:06:12,670 So that's what the inner loop is going to do. 133 133 00:06:12,670 --> 00:06:15,930 So we'll say for int, I equals zero 134 134 00:06:15,930 --> 00:06:19,010 because we always start at the beginning of the array. 135 135 00:06:19,010 --> 00:06:21,620 I less than the last unsorted index, 136 136 00:06:21,620 --> 00:06:25,730 because we don't need to go into the sorted partition 137 137 00:06:25,730 --> 00:06:27,260 because we know that those, the values 138 138 00:06:27,260 --> 00:06:29,210 in the sorted partition are already sorted. 139 139 00:06:29,210 --> 00:06:31,720 So in the inner loop, we start at zero 140 140 00:06:31,720 --> 00:06:35,163 and we keep going until we hit the last unsorted index. 141 141 00:06:36,479 --> 00:06:38,123 And we're gonna increment I, 142 142 00:06:39,370 --> 00:06:42,200 and then what we wanna do, is you saw in the slides, 143 143 00:06:42,200 --> 00:06:44,690 is we wanna compare the value at I 144 144 00:06:44,690 --> 00:06:46,920 with the value at I plus one. 145 145 00:06:46,920 --> 00:06:48,850 And if the value at I is greater than 146 146 00:06:48,850 --> 00:06:51,410 the value at I plus one, we wanna swap the two values 147 147 00:06:51,410 --> 00:06:53,470 because we wanna bubble the largest values 148 148 00:06:53,470 --> 00:06:55,300 up to the end of the array. 149 149 00:06:55,300 --> 00:07:00,300 And so we're going to say if intArray I 150 150 00:07:00,580 --> 00:07:04,923 is greater than intArray I plus one, 151 151 00:07:05,960 --> 00:07:07,960 well what do we want to do, we want to swap them. 152 152 00:07:07,960 --> 00:07:11,090 And we can use our swap method to do that. 153 153 00:07:11,090 --> 00:07:16,090 So we'll pass at the intArray, I and I plus one. 154 154 00:07:16,240 --> 00:07:18,700 And that's it, that's our implementation 155 155 00:07:18,700 --> 00:07:20,590 of the bubble sort algorithm, as I said 156 156 00:07:20,590 --> 00:07:22,600 this is not the only implementation, 157 157 00:07:22,600 --> 00:07:25,430 it is a implementation, or should that be 158 158 00:07:25,430 --> 00:07:26,860 an implementation. 159 159 00:07:26,860 --> 00:07:28,910 So we're sorting in ascending order, 160 160 00:07:28,910 --> 00:07:32,200 and we're bubbling large values to the end of the arrray, 161 161 00:07:32,200 --> 00:07:37,200 and we are growing the sorted partition from right to left. 162 162 00:07:37,207 --> 00:07:39,670 We're starting it right at the end of the array, 163 163 00:07:39,670 --> 00:07:42,690 and after each iteration of the outer loop, 164 164 00:07:42,690 --> 00:07:44,950 the sorted partition grows by one. 165 165 00:07:44,950 --> 00:07:47,720 And so it starts out being basically nothing 166 166 00:07:47,720 --> 00:07:50,120 in the sorted partition, and then it, 167 167 00:07:50,120 --> 00:07:53,640 after the first iteration, the element at position six 168 168 00:07:53,640 --> 00:07:56,440 is sorted, so that's a sorted partition, 169 169 00:07:56,440 --> 00:07:59,040 after two iterations, the elements at positions 170 170 00:07:59,040 --> 00:08:02,060 five and six are sorted, so that's the sorted partition 171 171 00:08:02,060 --> 00:08:03,630 et cetera until we get right down 172 172 00:08:03,630 --> 00:08:04,890 to the beginning of the array. 173 173 00:08:04,890 --> 00:08:08,180 So let's print out this array after we've sorted it. 174 174 00:08:08,180 --> 00:08:10,420 So for int I equals zero, 175 175 00:08:10,420 --> 00:08:15,220 I less than intArray.length, 176 176 00:08:15,220 --> 00:08:17,320 I plus plus, and we'll just print out 177 177 00:08:17,320 --> 00:08:21,800 the value in the arrays, so intArray I. 178 178 00:08:24,790 --> 00:08:25,970 So this should work. 179 179 00:08:25,970 --> 00:08:27,960 And when we run, these values should be sorted. 180 180 00:08:27,960 --> 00:08:29,010 Let's give it a shot. 181 181 00:08:33,830 --> 00:08:35,940 And sure enough, our values are sorted. 182 182 00:08:35,940 --> 00:08:36,773 22, -15, 1, 7, 183 183 00:08:39,163 --> 00:08:42,260 20, 35, and 55. 184 184 00:08:42,260 --> 00:08:46,150 I'll just close the console here, and so that's bubble sort. 185 185 00:08:46,150 --> 00:08:50,520 Now, I said in the last video that the time complexity 186 186 00:08:50,520 --> 00:08:53,760 of bubble sort is O to the N squared, it's quadratic. 187 187 00:08:53,760 --> 00:08:58,110 So the absolute worst case is it will take N squared 188 188 00:08:58,110 --> 00:09:01,820 steps where N is the number of items we're sorting. 189 189 00:09:01,820 --> 00:09:03,260 Now you might look at the code and say 190 190 00:09:03,260 --> 00:09:06,040 well it's not N squared, it's actually less than that 191 191 00:09:06,040 --> 00:09:09,840 because the sorted partition is growing 192 192 00:09:09,840 --> 00:09:12,500 after each iteration of the outer loop 193 193 00:09:12,500 --> 00:09:14,720 and the inner loop doesn't cross 194 194 00:09:14,720 --> 00:09:16,610 into the sorted partition. 195 195 00:09:16,610 --> 00:09:19,850 So the inner loop is actually doing less work 196 196 00:09:19,850 --> 00:09:22,530 as the algorithm progresses, or at least 197 197 00:09:22,530 --> 00:09:25,000 as this implementation progresses, and you'd be right. 198 198 00:09:25,000 --> 00:09:28,620 But remember that when it comes to determining 199 199 00:09:28,620 --> 00:09:32,440 the time complexity of an algorithm, we're not doing math. 200 200 00:09:32,440 --> 00:09:36,210 We don't want the absolute precise expression. 201 201 00:09:36,210 --> 00:09:38,950 What we're trying to do is get some sense 202 202 00:09:38,950 --> 00:09:42,120 of how the number of steps grows 203 203 00:09:42,120 --> 00:09:45,130 as the number of items we have to sort grows. 204 204 00:09:45,130 --> 00:09:47,470 So we kind of want a general idea. 205 205 00:09:47,470 --> 00:09:51,000 We want to be able to say this is a linear algorithm, 206 206 00:09:51,000 --> 00:09:52,990 or this is a quadratic algorithm, 207 207 00:09:52,990 --> 00:09:54,950 or this is a logarithmic algorithm, 208 208 00:09:54,950 --> 00:09:56,740 or this is a constant algorithm. 209 209 00:09:56,740 --> 00:09:58,820 It doesn't grow as the number of items 210 210 00:09:58,820 --> 00:10:00,270 you're dealing with grows. 211 211 00:10:00,270 --> 00:10:03,230 And so we're looking for approximations. 212 212 00:10:03,230 --> 00:10:06,720 The algorithm grows in a quadratic way 213 213 00:10:06,720 --> 00:10:08,670 as the number of items increases. 214 214 00:10:08,670 --> 00:10:11,220 The pattern isn't linear, it's not logarithmic, 215 215 00:10:11,220 --> 00:10:13,180 and it's certainly not constant. 216 216 00:10:13,180 --> 00:10:15,210 And so we still consider bubble sort 217 217 00:10:15,210 --> 00:10:17,270 to be an O to the N squared algorithm, 218 218 00:10:17,270 --> 00:10:19,320 and in fact this implementation 219 219 00:10:19,320 --> 00:10:21,590 has a little bit of an optimization. 220 220 00:10:21,590 --> 00:10:24,930 Strictly speaking, bubble sort wants us 221 221 00:10:24,930 --> 00:10:28,240 to traverse the entire array every single time. 222 222 00:10:28,240 --> 00:10:30,000 It doesn't really pay attention to where 223 223 00:10:30,000 --> 00:10:31,750 the sorted partition is. 224 224 00:10:31,750 --> 00:10:34,080 This implementation does pay attention 225 225 00:10:34,080 --> 00:10:35,600 to where the sorted partition is, 226 226 00:10:35,600 --> 00:10:37,810 and it doesn't cross into the sorted partition 227 227 00:10:37,810 --> 00:10:39,470 because it doesn't have to. 228 228 00:10:39,470 --> 00:10:41,470 Those elements are already sorted. 229 229 00:10:41,470 --> 00:10:44,890 One tip when it comes to determining time complexity 230 230 00:10:44,890 --> 00:10:46,670 is to look at how many loops there are. 231 231 00:10:46,670 --> 00:10:50,130 Because normally each loop corresponds to N, 232 232 00:10:50,130 --> 00:10:52,030 and so if you have only one loop, 233 233 00:10:52,030 --> 00:10:54,030 then it's linear time complexity. 234 234 00:10:54,030 --> 00:10:57,350 If you have two loops, then it's N times N. 235 235 00:10:57,350 --> 00:10:59,850 And so that's quadratic time complexity. 236 236 00:10:59,850 --> 00:11:03,260 And here we have two loops, and so just at a glance 237 237 00:11:03,260 --> 00:11:04,710 we can kind of guess that this is 238 238 00:11:04,710 --> 00:11:07,020 O to the N squared time complexity. 239 239 00:11:07,020 --> 00:11:10,170 Alright, so that's bubble sort, not very complex. 240 240 00:11:10,170 --> 00:11:12,950 As I said upfront in the theory video, 241 241 00:11:12,950 --> 00:11:17,010 this algorithm is one of the least efficient algorithms. 242 242 00:11:17,010 --> 00:11:18,800 In fact there are some computer scientists 243 243 00:11:18,800 --> 00:11:20,810 that think we shouldn't even teach it anymore, 244 244 00:11:20,810 --> 00:11:24,400 but it is a classic sort algorithm that is usually taught. 245 245 00:11:24,400 --> 00:11:27,580 And it's gotten us warmed up for some of the faster 246 246 00:11:27,580 --> 00:11:30,060 algorithms that we'll look at later. 247 247 00:11:30,060 --> 00:11:31,760 So I'll see you in the next video. 21512