Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,183 --> 00:00:02,766 (techno music) 2 2 00:00:05,320 --> 00:00:07,020 All right, so in the last video, 3 3 00:00:07,020 --> 00:00:09,640 we learned the insertion sort algorithm 4 4 00:00:09,640 --> 00:00:11,300 and you saw the implementation 5 5 00:00:11,300 --> 00:00:13,330 or at least one implementation, 6 6 00:00:13,330 --> 00:00:17,400 and I said that insertion sort is a quadratic algorithm 7 7 00:00:17,400 --> 00:00:21,920 and it is, but if the sequence of values 8 8 00:00:21,920 --> 00:00:25,000 that we're sorting is nearly sorted, 9 9 00:00:25,000 --> 00:00:29,010 then insertion sort runs in almost linear time 10 10 00:00:29,010 --> 00:00:31,560 and it does that because it doesn't have to do 11 11 00:00:31,560 --> 00:00:33,220 as much shifting. 12 12 00:00:33,220 --> 00:00:34,060 Think about it. 13 13 00:00:34,060 --> 00:00:36,720 If the most of the values are already sorted, 14 14 00:00:36,720 --> 00:00:40,000 then only a few values will actually have to be inserted 15 15 00:00:40,000 --> 00:00:41,620 into the sorted partition 16 16 00:00:41,620 --> 00:00:43,950 and the amount of shifting will be reduced. 17 17 00:00:43,950 --> 00:00:46,900 Now a computer scientist named Donald Shell 18 18 00:00:46,900 --> 00:00:49,320 realised that if we could cut down 19 19 00:00:49,320 --> 00:00:50,440 on the amount of shifting 20 20 00:00:50,440 --> 00:00:52,940 that insertion sort would run a lot faster 21 21 00:00:52,940 --> 00:00:54,680 and so he came up with something 22 22 00:00:54,680 --> 00:00:57,320 that's known as the Shell sort algorithm 23 23 00:00:57,320 --> 00:00:59,880 and that's what we're going to look at in this video. 24 24 00:00:59,880 --> 00:01:02,070 So how does Shell sort work? 25 25 00:01:02,070 --> 00:01:04,970 Well, it's a variation of insertion sort 26 26 00:01:04,970 --> 00:01:08,960 and what it does is insertion sort chooses 27 27 00:01:08,960 --> 00:01:12,650 which element to insert using a gap value of one. 28 28 00:01:12,650 --> 00:01:15,270 So every time insertion sort runs, 29 29 00:01:15,270 --> 00:01:18,370 it picks off the first unsorted value 30 30 00:01:18,370 --> 00:01:21,230 and then it compares that value to its neighbour 31 31 00:01:21,230 --> 00:01:23,300 and it keeps shifting the neighbours to the right 32 32 00:01:23,300 --> 00:01:26,050 until it finds the correct insertion point 33 33 00:01:26,050 --> 00:01:28,830 for the element that it's inserting. 34 34 00:01:28,830 --> 00:01:32,790 Shell sort starts out using a larger gap value, 35 35 00:01:32,790 --> 00:01:36,070 so instead of comparing elements to their neighbours, 36 36 00:01:36,070 --> 00:01:38,250 it compares elements that are farther apart 37 37 00:01:38,250 --> 00:01:40,060 from each other in the array. 38 38 00:01:40,060 --> 00:01:42,380 And then as the algorithm runs, 39 39 00:01:42,380 --> 00:01:45,390 it reduces the gap that it's using. 40 40 00:01:45,390 --> 00:01:46,970 And the goal is to reduce 41 41 00:01:46,970 --> 00:01:49,100 the amount of shifting that's required. 42 42 00:01:49,100 --> 00:01:51,330 So as I said, as the algorithm progresses, 43 43 00:01:51,330 --> 00:01:53,440 the gap value is reduced. 44 44 00:01:53,440 --> 00:01:57,020 So Shell sort traverses the array with a certain gap value 45 45 00:01:57,020 --> 00:01:59,460 and after it's done its first traversal 46 46 00:01:59,460 --> 00:02:00,910 with the initial gap value, 47 47 00:02:00,910 --> 00:02:03,960 it decreases the gap and it does it again 48 48 00:02:03,960 --> 00:02:07,110 and it does this and this is very important, 49 49 00:02:07,110 --> 00:02:11,470 it keeps reducing the gap value until the gap value is one. 50 50 00:02:11,470 --> 00:02:13,540 Now when the gap value is one, 51 51 00:02:13,540 --> 00:02:16,370 we're essentially doing an insertion sort. 52 52 00:02:16,370 --> 00:02:20,150 So the last iteration of the gap value 53 53 00:02:20,150 --> 00:02:22,310 will actually perform an insertion sort. 54 54 00:02:22,310 --> 00:02:24,000 But at that point, 55 55 00:02:24,000 --> 00:02:27,640 the array will be more sorted than it was at the beginning. 56 56 00:02:27,640 --> 00:02:30,360 And so essentially what Shell sort does 57 57 00:02:30,360 --> 00:02:32,520 is it does some preliminary work 58 58 00:02:32,520 --> 00:02:34,960 using gap values that are greater than one 59 59 00:02:34,960 --> 00:02:38,240 and that preliminary work puts the elements in the array 60 60 00:02:38,240 --> 00:02:41,330 and perhaps closer to their sorted positions 61 61 00:02:41,330 --> 00:02:43,760 and then at the very last iteration 62 62 00:02:43,760 --> 00:02:45,450 when the gap value becomes one, 63 63 00:02:45,450 --> 00:02:46,970 it does an insertion sort. 64 64 00:02:46,970 --> 00:02:50,520 But that final insertion sort will be working with values 65 65 00:02:50,520 --> 00:02:53,020 that have had some preliminary sorting done on them. 66 66 00:02:53,020 --> 00:02:54,040 And because of that, 67 67 00:02:54,040 --> 00:02:56,360 there will be a lot less shifting required. 68 68 00:02:56,360 --> 00:03:00,080 So one question is well, what do we use for the gap value? 69 69 00:03:00,080 --> 00:03:02,010 How do we figure out what to start with 70 70 00:03:02,010 --> 00:03:03,270 and how to reduce it? 71 71 00:03:03,270 --> 00:03:04,660 And you're going to see 72 72 00:03:04,660 --> 00:03:07,960 that there is a tonne of theories about this. 73 73 00:03:07,960 --> 00:03:10,870 We're going to go out now to the Wikipedia article 74 74 00:03:10,870 --> 00:03:12,143 about Shell sort. 75 75 00:03:16,820 --> 00:03:19,600 So here we are at the Wikipedia article 76 76 00:03:19,600 --> 00:03:21,330 that I've linked to in the resources 77 77 00:03:21,330 --> 00:03:25,730 and here's a table with different initial gap values 78 78 00:03:25,730 --> 00:03:27,530 and how to reduce the gap, 79 79 00:03:27,530 --> 00:03:30,240 what sequence of gap values to use. 80 80 00:03:30,240 --> 00:03:33,260 And as you can see, there's quite a number of them. 81 81 00:03:33,260 --> 00:03:34,810 The important thing to note 82 82 00:03:34,810 --> 00:03:37,360 is that the way that you calculate the gap 83 83 00:03:37,360 --> 00:03:39,750 can influence the time complexity. 84 84 00:03:39,750 --> 00:03:42,250 And so here we have a time complexity column 85 85 00:03:42,250 --> 00:03:44,090 and depending on what gap we're using, 86 86 00:03:44,090 --> 00:03:45,630 the time complexity is different. 87 87 00:03:45,630 --> 00:03:47,950 We have a logarithmic time complexity here. 88 88 00:03:47,950 --> 00:03:50,650 Here's a quadratic time complexity. 89 89 00:03:50,650 --> 00:03:54,960 And so the gap value you choose can influence 90 90 00:03:54,960 --> 00:03:58,620 how many steps the algorithm requires so keep that in mind. 91 91 00:03:58,620 --> 00:04:00,433 Let's go back to the slides. 92 92 00:04:05,750 --> 00:04:07,280 Okay, so there are a number of ways 93 93 00:04:07,280 --> 00:04:09,040 we can calculate the gap value. 94 94 00:04:09,040 --> 00:04:13,150 One really common sequence that's used for the gap value 95 95 00:04:13,150 --> 00:04:15,910 and the gap is also called the interval 96 96 00:04:15,910 --> 00:04:17,890 is the Knuth sequence. 97 97 00:04:17,890 --> 00:04:19,290 I think that's how it's pronounced. 98 98 00:04:19,290 --> 00:04:21,360 I've never pronounced it before or said it out loud 99 99 00:04:21,360 --> 00:04:23,690 so I don't know if the K is silent or not, 100 100 00:04:23,690 --> 00:04:26,420 but it's the Knuth sequence. 101 101 00:04:26,420 --> 00:04:29,560 And this says that we calculate the gap 102 102 00:04:29,560 --> 00:04:33,520 using three k minus one over two. 103 103 00:04:33,520 --> 00:04:37,750 And the initial value that we want to use 104 104 00:04:37,750 --> 00:04:39,920 is based on the length of the array. 105 105 00:04:39,920 --> 00:04:43,110 What we want is we want to use the value of k 106 106 00:04:43,110 --> 00:04:46,530 that's going to calculate to a value 107 107 00:04:46,530 --> 00:04:49,660 that's as close as possible to the length of the array 108 108 00:04:49,660 --> 00:04:51,380 without going over. 109 109 00:04:51,380 --> 00:04:55,850 And so if we had an array of let's say 20 elements, 110 110 00:04:55,850 --> 00:04:59,310 we would wanna start with k equal to three. 111 111 00:04:59,310 --> 00:05:02,230 If we were to start with k equals four, 112 112 00:05:02,230 --> 00:05:03,580 the gap would be 40 113 113 00:05:03,580 --> 00:05:05,800 and that's greater than the length of the array 114 114 00:05:05,800 --> 00:05:07,180 so that won't work. 115 115 00:05:07,180 --> 00:05:10,150 And so when you want to use this sequence, 116 116 00:05:10,150 --> 00:05:12,500 you want to start with the value of k 117 117 00:05:12,500 --> 00:05:16,410 that's going to result in a gap value 118 118 00:05:16,410 --> 00:05:20,560 that is as close to the array's length as possible 119 119 00:05:20,560 --> 00:05:21,930 without going over. 120 120 00:05:21,930 --> 00:05:24,580 Now in the implementation I'm going to show you, 121 121 00:05:24,580 --> 00:05:26,500 we're not going to use this sequence, 122 122 00:05:26,500 --> 00:05:31,440 but it's a common way of calculating the interval or the gap 123 123 00:05:31,440 --> 00:05:33,330 so I thought I'd show it to you. 124 124 00:05:33,330 --> 00:05:35,670 We're going to do something simpler than that. 125 125 00:05:35,670 --> 00:05:38,510 So what we're going to do is we're going to base our gap 126 126 00:05:38,510 --> 00:05:41,870 on the array's length and we're going to initialise the gap 127 127 00:05:41,870 --> 00:05:44,590 to array.length over two. 128 128 00:05:44,590 --> 00:05:45,970 And then on each iteration, 129 129 00:05:45,970 --> 00:05:50,310 we're going to divide the gap value by two until we hit one. 130 130 00:05:50,310 --> 00:05:53,750 Now our array only has seven elements in it 131 131 00:05:53,750 --> 00:05:56,950 and so the first gap value is going to be seven over two 132 132 00:05:56,950 --> 00:05:59,510 which is three and then the second gap value 133 133 00:05:59,510 --> 00:06:01,710 will be three over two which is one 134 134 00:06:01,710 --> 00:06:04,700 so we're actually only gonna have two iterations 135 135 00:06:04,700 --> 00:06:05,840 for this array. 136 136 00:06:05,840 --> 00:06:09,390 So on the first iteration, we'll use a gap value of three. 137 137 00:06:09,390 --> 00:06:10,940 And then on the final iteration, 138 138 00:06:10,940 --> 00:06:13,240 and this is always true for Shell sort, 139 139 00:06:13,240 --> 00:06:14,690 the gap value will be one. 140 140 00:06:14,690 --> 00:06:18,000 And at that point, we'll be doing an insertion sort. 141 141 00:06:18,000 --> 00:06:21,290 But because we've done a previous iteration 142 142 00:06:21,290 --> 00:06:23,730 and we've moved some of the elements around, 143 143 00:06:23,730 --> 00:06:25,390 some of the elements will be closer 144 144 00:06:25,390 --> 00:06:27,120 to their sorted positions. 145 145 00:06:27,120 --> 00:06:28,300 So let's go through this. 146 146 00:06:28,300 --> 00:06:30,900 So we're gonna start with a gap value of three 147 147 00:06:30,900 --> 00:06:33,500 because we're gonna use array.length over two. 148 148 00:06:33,500 --> 00:06:37,820 We're gonna initialise i to the gap and j to i. 149 149 00:06:37,820 --> 00:06:41,140 And as we did before with insertion sort, 150 150 00:06:41,140 --> 00:06:42,610 we're gonna save the value 151 151 00:06:42,610 --> 00:06:45,233 that we want to work with into newElement. 152 152 00:06:46,110 --> 00:06:48,590 And then what we do is we compare the element 153 153 00:06:48,590 --> 00:06:51,350 at index j minus gap 154 154 00:06:51,350 --> 00:06:55,240 so that will be three minus three is zero with newElement. 155 155 00:06:55,240 --> 00:06:58,310 So our gap is three and we're starting with element three 156 156 00:06:58,310 --> 00:07:00,310 so we basically wanna compare it. 157 157 00:07:00,310 --> 00:07:01,480 Because the gap is three, 158 158 00:07:01,480 --> 00:07:02,930 we wanna compare it to the element 159 159 00:07:02,930 --> 00:07:04,820 that's three positions away 160 160 00:07:04,820 --> 00:07:07,780 and so we compare seven with 20. 161 161 00:07:07,780 --> 00:07:10,010 Seven is less than 20 162 162 00:07:10,010 --> 00:07:11,900 and so what we're going to do 163 163 00:07:11,900 --> 00:07:15,490 is we're going to assign 20 to where seven was. 164 164 00:07:15,490 --> 00:07:19,360 So instead of doing what we were doing with insertion sort, 165 165 00:07:19,360 --> 00:07:21,360 which is we're comparing to the neighbours 166 166 00:07:21,360 --> 00:07:23,040 and shifting up one, 167 167 00:07:23,040 --> 00:07:27,360 we're comparing using a gap of three and we shift by three 168 168 00:07:27,360 --> 00:07:30,640 and so 20 has been shifted up three places. 169 169 00:07:30,640 --> 00:07:34,660 And then we're going to set j to j minus gap which is zero 170 170 00:07:34,660 --> 00:07:38,320 and we've hit the front of the array at this point 171 171 00:07:38,320 --> 00:07:41,550 and so what we're going to do is assign newElement 172 172 00:07:41,550 --> 00:07:43,490 to position zero. 173 173 00:07:43,490 --> 00:07:45,300 So what we've basically done 174 174 00:07:45,300 --> 00:07:47,210 is we're kind of doing an insertion sort 175 175 00:07:47,210 --> 00:07:48,600 but we're using a gap of three. 176 176 00:07:48,600 --> 00:07:53,600 So what we're gonna want to do next now is move i to four 177 177 00:07:53,940 --> 00:07:56,230 and j becomes i which is four, 178 178 00:07:56,230 --> 00:08:00,520 the newElement is 55 and we're gonna compare 55 to 35 179 179 00:08:01,670 --> 00:08:04,320 because that's three elements away. 180 180 00:08:04,320 --> 00:08:08,220 55 is greater than 35 so we don't do anything. 181 181 00:08:08,220 --> 00:08:10,270 Everything remains as it is. 182 182 00:08:10,270 --> 00:08:14,410 And now i will be five, j will be five, 183 183 00:08:14,410 --> 00:08:17,790 we're going to compare one to minus 15 184 184 00:08:17,790 --> 00:08:20,420 'cause minus 15 is three elements away. 185 185 00:08:20,420 --> 00:08:21,830 Okay, so there's nothing to do 186 186 00:08:21,830 --> 00:08:24,520 because one is greater than minus 15. 187 187 00:08:24,520 --> 00:08:29,350 And so now we're gonna move to minus 22 188 188 00:08:29,350 --> 00:08:31,737 and we're going to assign that to newElement 189 189 00:08:31,737 --> 00:08:33,890 and we're gonna compare it to the element 190 190 00:08:33,890 --> 00:08:36,740 that's three positions away from it 191 191 00:08:36,740 --> 00:08:39,850 and minus 22 is less than 20 192 192 00:08:39,850 --> 00:08:43,430 so we're going to assign 20 to position six. 193 193 00:08:43,430 --> 00:08:47,450 Now at this point, we're gonna subtract the gap from j 194 194 00:08:47,450 --> 00:08:50,440 and then we're going to compare minus 22 195 195 00:08:50,440 --> 00:08:52,900 against what's at position zero 196 196 00:08:52,900 --> 00:08:56,760 because we wanna go three elements away again. 197 197 00:08:56,760 --> 00:08:59,530 Minus 22 is less than seven 198 198 00:08:59,530 --> 00:09:03,440 so we're going to shift seven into position three. 199 199 00:09:03,440 --> 00:09:06,800 And at this point, we've hit the front of the array. 200 200 00:09:06,800 --> 00:09:10,070 There are no more elements to compare minus 22 against 201 201 00:09:10,070 --> 00:09:13,610 and so we assign minus 22 to position zero. 202 202 00:09:13,610 --> 00:09:17,740 And at that this point, we've hit the end of the array 203 203 00:09:17,740 --> 00:09:20,680 and so we have finished our first iteration 204 204 00:09:20,680 --> 00:09:22,980 with gap equal to three. 205 205 00:09:22,980 --> 00:09:26,360 Now notice that the array is more sorted now 206 206 00:09:26,360 --> 00:09:27,720 than it was before 207 207 00:09:27,720 --> 00:09:30,040 and we've moved minus 22 208 208 00:09:30,040 --> 00:09:31,660 all the way to the front of the array 209 209 00:09:31,660 --> 00:09:33,900 and we did that with one assignment. 210 210 00:09:33,900 --> 00:09:38,520 And so in insertion sort, pure insertion sort, 211 211 00:09:38,520 --> 00:09:40,850 at some point we would have had to have shifted 212 212 00:09:40,850 --> 00:09:44,640 minus 22 down or rather in the implementation I showed you 213 213 00:09:44,640 --> 00:09:47,390 every single element would have to have been shifted up 214 214 00:09:47,390 --> 00:09:49,660 to make room for minus 22. 215 215 00:09:49,660 --> 00:09:52,400 But in this sort of pre-sorting phase, 216 216 00:09:52,400 --> 00:09:54,320 when we're using a gap of three, 217 217 00:09:54,320 --> 00:09:56,900 minus 22 is moved very quickly down 218 218 00:09:56,900 --> 00:09:58,160 to the front of the array. 219 219 00:09:58,160 --> 00:10:00,920 We've also moved 20 closer to its sorted position. 220 220 00:10:00,920 --> 00:10:03,050 20 started at the front of the array 221 221 00:10:03,050 --> 00:10:05,480 and now it's only two positions away 222 222 00:10:05,480 --> 00:10:09,400 from where it usually ends up in the sorted array. 223 223 00:10:09,400 --> 00:10:12,300 So you can see how doing this preliminary work 224 224 00:10:12,300 --> 00:10:14,450 before we get to insertion sort 225 225 00:10:14,450 --> 00:10:17,230 will cut down on how much shifting we have to do. 226 226 00:10:17,230 --> 00:10:19,760 So at this point, we're gonna update the gap. 227 227 00:10:19,760 --> 00:10:23,100 We're gonna divide three by two and we'll get one 228 228 00:10:23,100 --> 00:10:24,380 and so at this point, 229 229 00:10:24,380 --> 00:10:26,650 we will actually do an insertion sort 230 230 00:10:26,650 --> 00:10:29,170 because the gap is going to be one 231 231 00:10:29,170 --> 00:10:31,830 so we're gonna be comparing everything to its neighbours 232 232 00:10:31,830 --> 00:10:34,510 and when we shift we're gonna be shifting up by one. 233 233 00:10:34,510 --> 00:10:37,030 And so at this point, we'll do an insertion sort, 234 234 00:10:37,030 --> 00:10:40,170 but we're doing an insertion sort on an array 235 235 00:10:40,170 --> 00:10:42,770 that has had some preliminary work done on it 236 236 00:10:42,770 --> 00:10:44,670 and so there's gonna be a lot less shifting 237 237 00:10:44,670 --> 00:10:46,980 and that's what Shell sort is all about. 238 238 00:10:46,980 --> 00:10:49,470 So Shell sort is an in-place algorithm 239 239 00:10:49,470 --> 00:10:50,800 just like insertion sort. 240 240 00:10:50,800 --> 00:10:53,010 We're working within the original array. 241 241 00:10:53,010 --> 00:10:54,070 Now as you saw, 242 242 00:10:54,070 --> 00:10:56,690 it's really difficult to nail down the time complexity 243 243 00:10:56,690 --> 00:10:58,960 because it's going to depend on the gap. 244 244 00:10:58,960 --> 00:11:01,660 It's gonna depend on the method that you're using 245 245 00:11:01,660 --> 00:11:03,650 to choose the gap. 246 246 00:11:03,650 --> 00:11:05,910 In the worse case, it can be quadratic. 247 247 00:11:05,910 --> 00:11:09,200 We saw that when we went out to the table in Wikipedia, 248 248 00:11:09,200 --> 00:11:11,570 but it can also perform much better than that. 249 249 00:11:11,570 --> 00:11:14,570 It doesn't require as much shifting as insertion sort. 250 250 00:11:14,570 --> 00:11:16,860 So as I said, it usually performs better 251 251 00:11:16,860 --> 00:11:17,960 than insertion sort. 252 252 00:11:17,960 --> 00:11:21,640 However, it's an unstable algorithm. 253 253 00:11:21,640 --> 00:11:24,470 Insertion sort is stable, 254 254 00:11:24,470 --> 00:11:27,560 but Shell sort is unstable and you can see why. 255 255 00:11:27,560 --> 00:11:30,320 It's because in the pre-insertion sort phase 256 256 00:11:30,320 --> 00:11:31,550 when we're comparing elements 257 257 00:11:31,550 --> 00:11:33,350 that are far away from each other, 258 258 00:11:33,350 --> 00:11:36,280 it's very possible that if we have a duplicate element, 259 259 00:11:36,280 --> 00:11:38,840 the rightmost element will be shifted 260 260 00:11:38,840 --> 00:11:42,440 in front of the leftmost element. 261 261 00:11:42,440 --> 00:11:44,870 So the fact that we're examining elements 262 262 00:11:44,870 --> 00:11:46,330 that are further away from each other 263 263 00:11:46,330 --> 00:11:50,460 can lead to the relative positions of duplicate items 264 264 00:11:50,460 --> 00:11:52,020 not being preserved. 265 265 00:11:52,020 --> 00:11:55,300 Now one last note before we go to the implementation. 266 266 00:11:55,300 --> 00:11:59,240 You can also improve bubble sort using Shell sort 267 267 00:11:59,240 --> 00:12:01,070 and it would be the same type of idea. 268 268 00:12:01,070 --> 00:12:03,330 You would use a gap interval. 269 269 00:12:03,330 --> 00:12:05,030 Remember in bubble sort, 270 270 00:12:05,030 --> 00:12:07,930 we're always comparing elements to their neighbours 271 271 00:12:07,930 --> 00:12:11,560 and then we're swapping and bubbling elements up. 272 272 00:12:11,560 --> 00:12:13,610 Well, it's the same sort of idea. 273 273 00:12:13,610 --> 00:12:16,640 So in bubble sort, if we use a gap of one, 274 274 00:12:16,640 --> 00:12:18,350 that means we compare it to the neighbours 275 275 00:12:18,350 --> 00:12:21,190 and everything gets swapped up one position. 276 276 00:12:21,190 --> 00:12:22,580 Things get bubbled up. 277 277 00:12:22,580 --> 00:12:24,900 If we do some preliminary work 278 278 00:12:24,900 --> 00:12:27,570 and in this case rather than just shifting elements, 279 279 00:12:27,570 --> 00:12:31,100 we'd actually swap them, we can improve bubble sort. 280 280 00:12:31,100 --> 00:12:35,447 So you can apply Shell sort to insertion sort 281 281 00:12:35,447 --> 00:12:39,010 and bubble sort and improve both algorithms that way. 282 282 00:12:39,010 --> 00:12:40,270 With insertion sort, 283 283 00:12:40,270 --> 00:12:42,530 you're cutting down on the number of shifting. 284 284 00:12:42,530 --> 00:12:44,010 And with bubble sort, 285 285 00:12:44,010 --> 00:12:46,680 you'd be cutting down on the number of swaps 286 286 00:12:46,680 --> 00:12:47,850 that you have to do. 287 287 00:12:47,850 --> 00:12:50,620 Okay, so that's it for taking a look at 288 288 00:12:50,620 --> 00:12:51,820 how the algorithm works. 289 289 00:12:51,820 --> 00:12:52,970 Let's implement it. 290 290 00:12:52,970 --> 00:12:54,520 I'll see you in the next video. 25311