Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,000 --> 00:00:02,100 (upbeat music) 2 2 00:00:02,100 --> 00:00:04,183 (typing) 3 3 00:00:05,410 --> 00:00:06,740 I said in the last video 4 4 00:00:06,740 --> 00:00:07,860 that we were gonna move on 5 5 00:00:07,860 --> 00:00:10,270 to the implementation of radix sort, 6 6 00:00:10,270 --> 00:00:12,470 but when I was looking over the implementation, 7 7 00:00:12,470 --> 00:00:15,440 I thought it would be helpful to go through 8 8 00:00:15,440 --> 00:00:19,230 the stable counting sort that we're going to use first, 9 9 00:00:19,230 --> 00:00:21,230 before we actually get to the implementation. 10 10 00:00:21,230 --> 00:00:22,970 So that's what we're gonna do in this video. 11 11 00:00:22,970 --> 00:00:26,070 So as I said in the video about counting sort, 12 12 00:00:26,070 --> 00:00:28,950 the implementation that I showed you was unstable. 13 13 00:00:28,950 --> 00:00:32,890 If you want it to be stable, we have to do some extra work. 14 14 00:00:32,890 --> 00:00:36,740 Now the implementation that I'm going to show you calculates 15 15 00:00:36,740 --> 00:00:40,700 where values should be written back to the original array, 16 16 00:00:40,700 --> 00:00:44,000 and then by writing the values into the array 17 17 00:00:44,000 --> 00:00:47,030 in backwards order, we get stability, 18 18 00:00:47,030 --> 00:00:49,700 and I think probably going through the slides 19 19 00:00:49,700 --> 00:00:51,370 will make this clear. 20 20 00:00:51,370 --> 00:00:54,860 In the last video, we went through sorting this array, 21 21 00:00:54,860 --> 00:00:59,040 and I'm going to go through the stable counting sort 22 22 00:00:59,040 --> 00:01:03,380 for when we sort the array based on the 10's position. 23 23 00:01:03,380 --> 00:01:05,160 And so if you look at the last video, 24 24 00:01:05,160 --> 00:01:08,220 we've already sorted based on the one's position, 25 25 00:01:08,220 --> 00:01:10,920 and we end up with the array on the screen, 26 26 00:01:10,920 --> 00:01:13,140 and now we're going to sort this array 27 27 00:01:13,140 --> 00:01:15,460 based on the 10's position, 28 28 00:01:15,460 --> 00:01:16,960 and the reason we're looking at the 10's 29 29 00:01:16,960 --> 00:01:19,740 is because the 10's actually have some duplicate values. 30 30 00:01:19,740 --> 00:01:21,780 So 1594 31 31 00:01:21,780 --> 00:01:25,370 has to remain after 8792 32 32 00:01:25,370 --> 00:01:26,620 after the sort, 33 33 00:01:26,620 --> 00:01:28,640 and 5729 34 34 00:01:28,640 --> 00:01:31,840 has to remain after 4725, 35 35 00:01:31,840 --> 00:01:33,400 'cause the sort has to be stable. 36 36 00:01:33,400 --> 00:01:37,580 So how are we gonna accomplish this using counting sort. 37 37 00:01:37,580 --> 00:01:42,580 So what we do, is we do the count just as we did before, 38 38 00:01:43,080 --> 00:01:45,770 and we're gonna end up with the counting array below. 39 39 00:01:45,770 --> 00:01:49,990 So we have two values that have two in the 10's position, 40 40 00:01:49,990 --> 00:01:52,190 4725 and 5729, 41 41 00:01:53,212 --> 00:01:57,310 1330 has a three in the 10's position, 42 42 00:01:57,310 --> 00:02:01,020 and then we don't have any fours, fives, sixes, or sevens 43 43 00:02:01,020 --> 00:02:02,480 in the 10's position. 44 44 00:02:02,480 --> 00:02:06,020 4586 has eight in the 10's position, 45 45 00:02:06,020 --> 00:02:07,370 and then we have two values 46 46 00:02:07,370 --> 00:02:09,620 with nine in the 10's position, 47 47 00:02:09,620 --> 00:02:12,240 8792 and 1594, 48 48 00:02:12,240 --> 00:02:15,370 and so our counting array is what you see in the bottom, 49 49 00:02:15,370 --> 00:02:20,240 zero, zero, two, one, zero, zero, zero, zero, one, two, 50 50 00:02:20,240 --> 00:02:23,320 and so that tells us we have two values with a two 51 51 00:02:23,320 --> 00:02:24,560 in the 10's position, 52 52 00:02:24,560 --> 00:02:27,740 one value with three in the 10's position, 53 53 00:02:27,740 --> 00:02:30,300 one value with eight in the 10's position, 54 54 00:02:30,300 --> 00:02:33,050 and two values with nine in the 10's position, 55 55 00:02:33,050 --> 00:02:34,480 and that's all fine and dandy 56 56 00:02:34,480 --> 00:02:36,100 but how are we gonna write these values back? 57 57 00:02:36,100 --> 00:02:38,160 'Cause we don't actually have the values 58 58 00:02:38,160 --> 00:02:39,450 in the counting array, 59 59 00:02:39,450 --> 00:02:42,020 and on top of that, we want the sort to be stable. 60 60 00:02:42,020 --> 00:02:44,640 And so what we're gonna so is we're going to create 61 61 00:02:44,640 --> 00:02:47,360 a temporary array that matches the length 62 62 00:02:47,360 --> 00:02:48,570 of the array we're sorting. 63 63 00:02:48,570 --> 00:02:49,590 And so we're going to create 64 64 00:02:49,590 --> 00:02:51,790 a temporary array of length six, 65 65 00:02:51,790 --> 00:02:54,700 because we're sorting six values. 66 66 00:02:54,700 --> 00:02:57,020 And we can use the counts to figure out 67 67 00:02:57,020 --> 00:03:00,090 which range of indices in the temporary array 68 68 00:03:00,090 --> 00:03:01,850 will be occupied by each value. 69 69 00:03:01,850 --> 00:03:02,880 For example, 70 70 00:03:02,880 --> 00:03:05,310 because we don't have any zeros 71 71 00:03:05,310 --> 00:03:07,740 in the 10's position and any ones, 72 72 00:03:07,740 --> 00:03:11,080 we know that the two values that have a two 73 73 00:03:11,080 --> 00:03:13,560 in the 10's position are going to occupy 74 74 00:03:13,560 --> 00:03:17,050 positions zero and one in the sorted array. 75 75 00:03:17,050 --> 00:03:19,810 And then we have one value with a three 76 76 00:03:19,810 --> 00:03:20,880 in the 10's position, 77 77 00:03:20,880 --> 00:03:23,100 so we know that'll go into position two. 78 78 00:03:23,100 --> 00:03:25,530 And then we don't have any values 79 79 00:03:25,530 --> 00:03:27,650 with four, five, six, and seven, 80 80 00:03:27,650 --> 00:03:30,150 but we have one value with an eight, 81 81 00:03:30,150 --> 00:03:32,890 so we know that's going to go into position three, 82 82 00:03:32,890 --> 00:03:35,140 and then positions four and five are gonna hold 83 83 00:03:35,140 --> 00:03:38,400 the two values that have a nine in the 10's position. 84 84 00:03:38,400 --> 00:03:41,250 So because we know how many values we're sorting, 85 85 00:03:41,250 --> 00:03:43,820 and because we know how many of each value 86 86 00:03:43,820 --> 00:03:46,460 have a specific digit in their 10's position, 87 87 00:03:46,460 --> 00:03:50,647 we can figure out what range of positions the values 88 88 00:03:50,647 --> 00:03:55,210 with a specific digit in the 10's position are gonna occupy. 89 89 00:03:55,210 --> 00:03:57,280 The way that we figure out these ranges is 90 90 00:03:57,280 --> 00:04:00,060 after we've done our first counting pass, 91 91 00:04:00,060 --> 00:04:02,880 and we've ended up with our usual counting array, 92 92 00:04:02,880 --> 00:04:04,760 we adjust the counts. 93 93 00:04:04,760 --> 00:04:07,410 So instead of just keeping the number of values 94 94 00:04:07,410 --> 00:04:09,620 that have a specific 10's digit, 95 95 00:04:09,620 --> 00:04:11,710 we want to store how many values 96 96 00:04:11,710 --> 00:04:14,700 have a specific 10's digit or less. 97 97 00:04:14,700 --> 00:04:17,820 So for example, at index three in the counting array, 98 98 00:04:17,820 --> 00:04:20,380 which currently contains the number of values 99 99 00:04:20,380 --> 00:04:22,830 that have a three in the 10's position. 100 100 00:04:22,830 --> 00:04:25,530 Instead of that, we want to know how many values 101 101 00:04:25,530 --> 00:04:28,560 have three or less in the 10's position, 102 102 00:04:28,560 --> 00:04:30,930 and in this case that's three values right? 103 103 00:04:30,930 --> 00:04:33,170 Because we have two values that have two 104 104 00:04:33,170 --> 00:04:34,390 in the 10's position 105 105 00:04:34,390 --> 00:04:36,970 and one value that has three in the 10's position, 106 106 00:04:36,970 --> 00:04:39,160 and so we have three values 107 107 00:04:39,160 --> 00:04:43,500 that have a three or less in the 10's position. 108 108 00:04:43,500 --> 00:04:46,070 And we can calculate how many values 109 109 00:04:46,070 --> 00:04:49,330 have a specific digit or less by summing up 110 110 00:04:49,330 --> 00:04:52,640 all the counts that come before it. 111 111 00:04:52,640 --> 00:04:57,100 And so for example, by summing up zero, zero, two, and one, 112 112 00:04:57,100 --> 00:04:59,870 we get three, and that's how many values 113 113 00:04:59,870 --> 00:05:03,360 have a three or less in the 10's position, right? 114 114 00:05:03,360 --> 00:05:06,730 Because we don't have any values with zero, 115 115 00:05:06,730 --> 00:05:07,970 we don't have any values with one, 116 116 00:05:07,970 --> 00:05:11,150 we have two values with two and one value with three. 117 117 00:05:11,150 --> 00:05:14,920 And so after we've adjusted our counts, this is what we get. 118 118 00:05:14,920 --> 00:05:18,080 So we don't have any values with zero. 119 119 00:05:18,080 --> 00:05:20,270 We don't have any values with one or less. 120 120 00:05:20,270 --> 00:05:23,330 We have two values with two or less. 121 121 00:05:23,330 --> 00:05:25,570 We have three values with three or less, 122 122 00:05:25,570 --> 00:05:27,750 and then three values with four or less, 123 123 00:05:27,750 --> 00:05:29,680 three values with five or less. 124 124 00:05:29,680 --> 00:05:31,670 Up to the value for eight, 125 125 00:05:31,670 --> 00:05:34,410 where we have four values that have eight or less, 126 126 00:05:34,410 --> 00:05:37,950 and then finally we have six values with nine or less, 127 127 00:05:37,950 --> 00:05:39,590 and that last position 128 128 00:05:39,590 --> 00:05:43,840 is always gonna basically equal the number of values we have 129 129 00:05:43,840 --> 00:05:46,500 because everything in the array is gonna have 130 130 00:05:46,500 --> 00:05:49,800 the highest possible digit or letter, or less. 131 131 00:05:49,800 --> 00:05:53,020 And so this is our adjusted count array, 132 132 00:05:53,020 --> 00:05:57,240 where each element, instead of containing the exact count 133 133 00:05:57,240 --> 00:05:58,360 of how many values 134 134 00:05:58,360 --> 00:06:01,480 have a specific digit in their 10's position, 135 135 00:06:01,480 --> 00:06:03,090 instead it contains a count 136 136 00:06:03,090 --> 00:06:06,330 of how many values have that digit or less. 137 137 00:06:06,330 --> 00:06:08,110 And now we're going to use that 138 138 00:06:08,110 --> 00:06:09,890 to write back to our input array. 139 139 00:06:09,890 --> 00:06:13,680 So the code at the top is what we're going to use. 140 140 00:06:13,680 --> 00:06:17,100 So we initialise our temp array, 141 141 00:06:17,100 --> 00:06:20,290 and n is the number of elements we're sorting. 142 142 00:06:20,290 --> 00:06:22,890 So we'll have a temp array of length six. 143 143 00:06:22,890 --> 00:06:26,690 And then, we traverse the array backwards. 144 144 00:06:26,690 --> 00:06:29,280 So we traverse the array from right to left, 145 145 00:06:29,280 --> 00:06:32,160 because this is going to make us write 146 146 00:06:32,160 --> 00:06:35,110 the rightmost values before the leftmost values 147 147 00:06:35,110 --> 00:06:37,380 and that's what's going to ensure stability. 148 148 00:06:37,380 --> 00:06:39,480 And so we start with n of six, 149 149 00:06:39,480 --> 00:06:41,400 k is gonna go from five to zero. 150 150 00:06:41,400 --> 00:06:43,380 So when k is five, 151 151 00:06:43,380 --> 00:06:47,190 we're going to get the digit in the 10's position, 152 152 00:06:47,190 --> 00:06:49,780 that's what that getDigit method is doing, 153 153 00:06:49,780 --> 00:06:52,710 and we're going to get it for input k, 154 154 00:06:52,710 --> 00:06:54,250 and k is starting at five. 155 155 00:06:54,250 --> 00:06:55,650 So if we go back, 156 156 00:06:55,650 --> 00:06:57,930 that's 5729. 157 157 00:06:57,930 --> 00:06:59,813 We're going to look at countArray[2], 158 158 00:07:00,870 --> 00:07:02,920 because we're going to figure out that 159 159 00:07:04,426 --> 00:07:07,140 the getDigit call is going to return two. 160 160 00:07:07,140 --> 00:07:09,910 And so we're gonna index countArray[2], 161 161 00:07:09,910 --> 00:07:12,860 and we're using the prefix operator 162 162 00:07:12,860 --> 00:07:16,170 so we're gonna subtract one from countArray[2], 163 163 00:07:16,170 --> 00:07:17,760 that's gonna give us one. 164 164 00:07:17,760 --> 00:07:20,160 And then we're going to assign input k, 165 165 00:07:20,160 --> 00:07:23,490 which we just saw back here is 5729. 166 166 00:07:23,490 --> 00:07:26,360 We're gonna assign that into tmp[1]. 167 167 00:07:26,360 --> 00:07:28,270 So let's go through that one more time. 168 168 00:07:28,270 --> 00:07:30,890 We're going to get the digit 169 169 00:07:30,890 --> 00:07:33,650 of input five, 170 170 00:07:33,650 --> 00:07:34,750 the 10's digit, 171 171 00:07:34,750 --> 00:07:38,750 and that digit is two, 'cause we're dealing with 5729. 172 172 00:07:38,750 --> 00:07:42,080 And then we're going to decrement the value at countArray[2] 173 173 00:07:42,080 --> 00:07:43,580 which is gonna give us one. 174 174 00:07:43,580 --> 00:07:46,450 And then we're going to use that result as the index 175 175 00:07:46,450 --> 00:07:47,950 into our temp array. 176 176 00:07:47,950 --> 00:07:51,360 So we're gonna assign input of k, input five, 177 177 00:07:51,360 --> 00:07:53,000 which is 5729, 178 178 00:07:53,000 --> 00:07:55,860 into temp at position one. 179 179 00:07:55,860 --> 00:07:58,090 And so we're gonna end up with this situation, 180 180 00:07:58,090 --> 00:08:00,230 where we have 5729 181 181 00:08:00,230 --> 00:08:01,690 in the temp array. 182 182 00:08:01,690 --> 00:08:03,500 So now we have the temp array at the top, 183 183 00:08:03,500 --> 00:08:05,070 and our count array at the bottom. 184 184 00:08:05,070 --> 00:08:08,330 Now we've decremented countArray[2] by one, 185 185 00:08:08,330 --> 00:08:10,110 because we're written one value 186 186 00:08:10,110 --> 00:08:11,900 with two in the 10's position, 187 187 00:08:11,900 --> 00:08:16,380 and notice that it's gone into temp array one. 188 188 00:08:16,380 --> 00:08:18,630 And so the second value that has two 189 189 00:08:18,630 --> 00:08:20,680 is gonna go into temp array zero. 190 190 00:08:20,680 --> 00:08:25,070 And because we're going right to left in the input array, 191 191 00:08:25,070 --> 00:08:28,730 we're writing rightmost values before leftmost values. 192 192 00:08:28,730 --> 00:08:30,510 So that means if we have a duplicate, 193 193 00:08:30,510 --> 00:08:32,600 the rightmost duplicate will be written 194 194 00:08:32,600 --> 00:08:34,760 to the right of the leftmost duplicate, 195 195 00:08:34,760 --> 00:08:36,980 and that's what's preserving the stability. 196 196 00:08:36,980 --> 00:08:40,170 And so now k is gonna get decremented to four. 197 197 00:08:40,170 --> 00:08:43,310 We're gonna be handling value 4586. 198 198 00:08:43,310 --> 00:08:45,590 The 10's digit is eight. 199 199 00:08:45,590 --> 00:08:48,530 So we're gonna decrement countArray[8] by one, 200 200 00:08:48,530 --> 00:08:49,730 which will give us three, 201 201 00:08:49,730 --> 00:08:54,730 and so we're gonna assign 4586 into temp at position three. 202 202 00:08:55,280 --> 00:08:57,740 And we're gonna end up with this situation. 203 203 00:08:57,740 --> 00:09:02,740 So 4586 has gone into the temporary array at position three, 204 204 00:09:02,891 --> 00:09:05,730 and countArray[8] is now three, 205 205 00:09:05,730 --> 00:09:07,900 because we've decremented it by one 206 206 00:09:07,900 --> 00:09:10,180 'cause we've written out one value was eight 207 207 00:09:10,180 --> 00:09:11,830 in the 10's position. 208 208 00:09:11,830 --> 00:09:15,980 So now k will be three, so we're gonna be handling 4725, 209 209 00:09:15,980 --> 00:09:18,310 that has a two in the 10's position. 210 210 00:09:18,310 --> 00:09:20,420 We're gonna decrement countArray[2] 211 211 00:09:20,420 --> 00:09:22,400 so that's gonna become zero. 212 212 00:09:22,400 --> 00:09:26,260 And so we're gonna assign 4725 to temp zero. 213 213 00:09:26,260 --> 00:09:28,160 And so this is our array, 214 214 00:09:28,160 --> 00:09:32,220 and notice that we have preserved the relative positions 215 215 00:09:32,220 --> 00:09:35,380 of 4725 and 5729, 216 216 00:09:35,380 --> 00:09:37,360 because we're going right to left. 217 217 00:09:37,360 --> 00:09:40,390 So when we write the rightmost duplicate value, 218 218 00:09:40,390 --> 00:09:43,970 we write that value into the rightmost position 219 219 00:09:43,970 --> 00:09:48,050 of the set of positions for that 10's value. 220 220 00:09:48,050 --> 00:09:50,650 And so we knew that the two values 221 221 00:09:50,650 --> 00:09:53,120 that have a two in the 10's position 222 222 00:09:53,120 --> 00:09:55,700 were gonna occupy positions zero and one. 223 223 00:09:55,700 --> 00:09:59,210 And so we write the rightmost value in the original array 224 224 00:09:59,210 --> 00:10:00,630 into position one, 225 225 00:10:00,630 --> 00:10:02,850 and the leftmost value into position zero. 226 226 00:10:02,850 --> 00:10:05,520 And by doing that we have preserved the relative positions. 227 227 00:10:05,520 --> 00:10:07,740 So this is a stable sort. 228 228 00:10:07,740 --> 00:10:11,090 And you'll notice now that countArray[2] is zero 229 229 00:10:11,090 --> 00:10:13,700 because we've now written out both values 230 230 00:10:13,700 --> 00:10:16,230 with two in the 10's position. 231 231 00:10:16,230 --> 00:10:17,810 So now when k equals two, 232 232 00:10:17,810 --> 00:10:20,880 we're gonna be handling value 1594, 233 233 00:10:20,880 --> 00:10:23,050 it has a nine in the 10's position 234 234 00:10:23,050 --> 00:10:25,430 so we're gonna decrement countArray[9]. 235 235 00:10:25,430 --> 00:10:27,070 It'll become five, 236 236 00:10:27,070 --> 00:10:31,260 and then we assign 1594 to temp five. 237 237 00:10:31,260 --> 00:10:34,730 And so the rightmost value with nine 238 238 00:10:34,730 --> 00:10:37,950 is being written in the rightmost position, 239 239 00:10:37,950 --> 00:10:41,180 for values that have nine in the 10's position. 240 240 00:10:41,180 --> 00:10:44,600 k will be one, we'll handle 8792. 241 241 00:10:44,600 --> 00:10:47,090 We decrement countArray[9] to four, 242 242 00:10:47,090 --> 00:10:50,400 and we assign 8792 to temp four, 243 243 00:10:50,400 --> 00:10:51,630 and we have preserved 244 244 00:10:51,630 --> 00:10:56,260 the relative positions of 8792 and 1594. 245 245 00:10:56,260 --> 00:11:00,580 And then finally k will be zero, we'll handle 1330. 246 246 00:11:00,580 --> 00:11:04,590 We'll subtract one from countArray[3] to get two, 247 247 00:11:04,590 --> 00:11:08,670 and we'll write 1330 to position two in the temporary array. 248 248 00:11:08,670 --> 00:11:09,503 And there we go, 249 249 00:11:09,503 --> 00:11:12,370 we have completed our sort of the values 250 250 00:11:12,370 --> 00:11:14,130 based on the 10's position, 251 251 00:11:14,130 --> 00:11:18,280 and the relative positioning of any duplicates 252 252 00:11:18,280 --> 00:11:19,970 have been preserved. 253 253 00:11:19,970 --> 00:11:22,810 And so this is a stable counting sort. 254 254 00:11:22,810 --> 00:11:24,450 It works because we traverse 255 255 00:11:24,450 --> 00:11:26,300 the input array from right to left, 256 256 00:11:26,300 --> 00:11:27,990 and we write duplicate values 257 257 00:11:27,990 --> 00:11:30,940 into the temp array from right to left. 258 258 00:11:30,940 --> 00:11:33,750 So if we know that duplicate values will go into, 259 259 00:11:33,750 --> 00:11:36,240 let's say positions three and four, 260 260 00:11:36,240 --> 00:11:38,990 we write the rightmost value in the input array 261 261 00:11:38,990 --> 00:11:40,330 into position four 262 262 00:11:40,330 --> 00:11:43,010 and the leftmost value into position three, 263 263 00:11:43,010 --> 00:11:45,150 and this preserves the relative positioning 264 264 00:11:45,150 --> 00:11:46,810 of duplicate values. 265 265 00:11:46,810 --> 00:11:49,380 And so by adjusting the counting array 266 266 00:11:49,380 --> 00:11:50,970 after the initial pass, 267 267 00:11:50,970 --> 00:11:53,880 so that we, instead of storing just the raw counts, 268 268 00:11:53,880 --> 00:11:56,300 instead we store how many values 269 269 00:11:56,300 --> 00:11:59,270 have that value or less. 270 270 00:11:59,270 --> 00:12:01,050 So for us, it was how many values 271 271 00:12:01,050 --> 00:12:05,300 have a specific digit or less in the 10's position. 272 272 00:12:05,300 --> 00:12:07,620 We can use those adjusted counts 273 273 00:12:07,620 --> 00:12:12,070 to map values back to indices in the temp array. 274 274 00:12:12,070 --> 00:12:13,360 Now another way of doing this 275 275 00:12:13,360 --> 00:12:15,100 is to use something called linked lists, 276 276 00:12:15,100 --> 00:12:16,430 we haven't covered those yet. 277 277 00:12:16,430 --> 00:12:17,970 We'll be covering those soon. 278 278 00:12:17,970 --> 00:12:19,120 But another way of doing this, 279 279 00:12:19,120 --> 00:12:21,680 is instead of just using counts the way that we did, 280 280 00:12:21,680 --> 00:12:25,230 you can actually store a list of the actual values 281 281 00:12:25,230 --> 00:12:26,790 at each position in a count array, 282 282 00:12:26,790 --> 00:12:29,760 and then you write the list out backwards. 283 283 00:12:29,760 --> 00:12:32,110 So we're not gonna cover that, 284 284 00:12:32,110 --> 00:12:33,720 because we haven't covered linked lists yet, 285 285 00:12:33,720 --> 00:12:35,380 but that's another way that you could do it. 286 286 00:12:35,380 --> 00:12:38,780 Now obviously we've sorted into a temporary array, 287 287 00:12:38,780 --> 00:12:42,600 so at this step here the top array is a temporary array. 288 288 00:12:42,600 --> 00:12:44,920 So obviously there would be one more step, 289 289 00:12:44,920 --> 00:12:46,920 and that would be copying the temporary array 290 290 00:12:46,920 --> 00:12:49,620 back into the input array. 291 291 00:12:49,620 --> 00:12:52,150 Okay so that's it for the stable counting sort. 292 292 00:12:52,150 --> 00:12:54,900 The code up here is the code 293 293 00:12:54,900 --> 00:12:58,530 that we're actually gonna use in the implementations. 294 294 00:12:58,530 --> 00:12:59,810 So now that you've seen it, 295 295 00:12:59,810 --> 00:13:02,640 when we code the implementation, I won't have to spend time 296 296 00:13:02,640 --> 00:13:05,480 trying to explain to you what's going on, 297 297 00:13:05,480 --> 00:13:06,940 and not having any slides to do it. 298 298 00:13:06,940 --> 00:13:09,160 So I thought that having slides and going through it 299 299 00:13:09,160 --> 00:13:11,270 would make it easier for you to understand. 300 300 00:13:11,270 --> 00:13:12,550 So now finally, 301 301 00:13:12,550 --> 00:13:15,470 let's move on to the implementation of radix sort. 302 302 00:13:15,470 --> 00:13:17,020 I'll see you in the next video. 26155