Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,199 --> 00:00:05,199 (lively music) (keyboard clacking) 2 2 00:00:05,970 --> 00:00:07,440 So, let's implement radix sort. 3 3 00:00:07,440 --> 00:00:09,580 I've created a project, I've put the code 4 4 00:00:09,580 --> 00:00:12,960 into package academy.learnprogramming.radixsort. 5 5 00:00:12,960 --> 00:00:15,880 I've created our array that we're going to sort, 6 6 00:00:15,880 --> 00:00:18,400 it's the same array that we went through in the slides 7 7 00:00:18,400 --> 00:00:21,780 and I have code for printing out the array after the sort. 8 8 00:00:21,780 --> 00:00:23,120 We're gonna create two methods, 9 9 00:00:23,120 --> 00:00:27,790 one called radixSort and one called radixSingleSort 10 10 00:00:27,790 --> 00:00:29,420 and you'll see what those do in a minute, 11 11 00:00:29,420 --> 00:00:30,703 so let's start with radixSort, 12 12 00:00:30,703 --> 00:00:35,373 so I'll say public static void radixSort. 13 13 00:00:36,725 --> 00:00:38,475 We've gonna accept our input array, 14 14 00:00:40,280 --> 00:00:42,893 the radix and the width. 15 15 00:00:43,900 --> 00:00:45,790 Remember that for radixSort, 16 16 00:00:45,790 --> 00:00:47,927 all the values have to have the same radix 17 17 00:00:47,927 --> 00:00:49,570 and the same width 18 18 00:00:49,570 --> 00:00:54,240 and then we're gonna say for int i equals zero, 19 19 00:00:54,240 --> 00:00:56,550 i less than width, 20 20 00:00:56,550 --> 00:01:01,550 i++ and we're gonna call the radixSingleSort method 21 21 00:01:02,010 --> 00:01:03,680 that we haven't written yet 22 22 00:01:03,680 --> 00:01:08,543 and we're gonna pass the input i and the radix. 23 23 00:01:09,760 --> 00:01:11,390 And so, basically what we're doing here 24 24 00:01:11,390 --> 00:01:13,510 is we're gonna call radixSingleSort 25 25 00:01:13,510 --> 00:01:17,350 for each position in our values 26 26 00:01:17,350 --> 00:01:20,340 and so, we have a width of four 27 27 00:01:20,340 --> 00:01:22,270 and so, we're gonna loop four times 28 28 00:01:22,270 --> 00:01:24,940 and each time we call radixSingleSort, 29 29 00:01:24,940 --> 00:01:28,300 it'll do the sort based on one of the positions 30 30 00:01:28,300 --> 00:01:31,300 and as you'll see, it'll start with the rightmost position 31 31 00:01:31,300 --> 00:01:36,210 and then move to the rightmost minus one position et cetera, 32 32 00:01:36,210 --> 00:01:38,340 so it'll be moving along the digits 33 33 00:01:38,340 --> 00:01:40,590 from the least significant digit 34 34 00:01:40,590 --> 00:01:43,470 to the most significant digit from right to left. 35 35 00:01:43,470 --> 00:01:46,320 So, let's write the radixSingleSort method, 36 36 00:01:46,320 --> 00:01:50,200 so we'll say public static void radixSingleSort 37 37 00:01:51,040 --> 00:01:53,093 and it takes the input array, 38 38 00:01:56,760 --> 00:02:00,413 the position and the radix. 39 39 00:02:05,156 --> 00:02:06,190 And so, the first thing we're gonna do 40 40 00:02:06,190 --> 00:02:08,700 is we're gonna say int numItems 41 41 00:02:08,700 --> 00:02:12,750 equals the input array dot length, 42 42 00:02:12,750 --> 00:02:15,310 so this just stores how many items 43 43 00:02:15,310 --> 00:02:16,920 that we're gonna be sorting. 44 44 00:02:16,920 --> 00:02:20,690 And then we're gonna say int countArray equals 45 45 00:02:20,690 --> 00:02:25,690 and we're going to create a countArray 46 46 00:02:26,480 --> 00:02:28,890 that's large enough to hold all the possible values, 47 47 00:02:28,890 --> 00:02:32,900 our radix will be 10 'cause we will have digit zero to nine 48 48 00:02:32,900 --> 00:02:35,570 and so, we'll have a countArray of length 10 49 49 00:02:36,850 --> 00:02:40,947 and then we're gonna say for int value: input, 50 50 00:02:42,810 --> 00:02:46,543 so for every value in our input array, 51 51 00:02:48,130 --> 00:02:53,130 we're gonna count how many values have a certain digit 52 52 00:02:53,200 --> 00:02:55,110 in whatever position we're looking at, 53 53 00:02:55,110 --> 00:02:57,910 so we're gonna call getDigit 54 54 00:02:57,910 --> 00:03:00,298 and we're gonna write this method in a minute 55 55 00:03:00,298 --> 00:03:02,550 and we're gonna pass the position and the value 56 56 00:03:02,550 --> 00:03:05,483 and the radix. 57 57 00:03:06,750 --> 00:03:10,730 And this method is going to return the digit, 58 58 00:03:10,730 --> 00:03:13,180 so it's gonna return zero to nine 59 59 00:03:13,180 --> 00:03:16,540 and then we're going to increment the count by one, 60 60 00:03:16,540 --> 00:03:20,400 so when we pass the first value, 4725, 61 61 00:03:20,400 --> 00:03:23,320 five's gonna come back as the digit 62 62 00:03:23,320 --> 00:03:27,560 and so, we're gonna increment countArray five by one. 63 63 00:03:27,560 --> 00:03:29,080 So, before we go any further, 64 64 00:03:29,080 --> 00:03:31,018 let's write the getDigit, 65 65 00:03:31,018 --> 00:03:32,530 I'm just gonna remove this blank line here, 66 66 00:03:32,530 --> 00:03:33,690 we don't really need it. 67 67 00:03:33,690 --> 00:03:35,670 Let's write the getDigit method, 68 68 00:03:35,670 --> 00:03:37,220 so you can see what it does. 69 69 00:03:37,220 --> 00:03:41,273 So, we'll say public static int getDigit, 70 70 00:03:43,100 --> 00:03:44,693 it accepts a position, 71 71 00:03:45,990 --> 00:03:48,043 a value and the radix. 72 72 00:03:49,890 --> 00:03:52,633 And it's not a difficult method. 73 73 00:03:52,633 --> 00:03:54,980 It's gonna return value over, 74 74 00:03:54,980 --> 00:03:57,160 we're gonna pass this to int 75 75 00:03:57,160 --> 00:04:00,160 because we don't want to have 76 76 00:04:00,160 --> 00:04:03,250 a floating point value returned. 77 77 00:04:03,250 --> 00:04:08,250 I'm just gonna pass Math.pow 10, position 78 78 00:04:10,920 --> 00:04:15,680 modded by the radix. 79 79 00:04:15,680 --> 00:04:17,620 So, what the heck is this doing? 80 80 00:04:17,620 --> 00:04:20,970 The Math.pow method takes the first parameter 81 81 00:04:20,970 --> 00:04:22,980 and raises it to the second parameter. 82 82 00:04:22,980 --> 00:04:24,780 We've passed in position zero 83 83 00:04:24,780 --> 00:04:27,070 because here we're starting at zero, 84 84 00:04:27,070 --> 00:04:29,220 so we've passed in zero for the position, 85 85 00:04:29,220 --> 00:04:32,690 we have 4725 for the value and 10 for the radix 86 86 00:04:32,690 --> 00:04:36,500 and so, we're gonna get Math.pow 10 raised to the zero 87 87 00:04:36,500 --> 00:04:38,370 which is one, 'cause anything raised 88 88 00:04:38,370 --> 00:04:40,221 to the zero power is one 89 89 00:04:40,221 --> 00:04:43,940 and the division operator takes precedence 90 90 00:04:43,940 --> 00:04:45,670 over the modulo operator, 91 91 00:04:45,670 --> 00:04:50,390 so we're gonna divided the value by one, 4725 divided by one 92 92 00:04:50,390 --> 00:04:52,600 is obviously 4725 93 93 00:04:52,600 --> 00:04:55,750 and then we're gonna mod that by the radix which is 10. 94 94 00:04:55,750 --> 00:04:59,633 Well, 4725 divided by 10 is 472 95 95 00:05:00,820 --> 00:05:02,520 and the remainder's gonna be five 96 96 00:05:02,520 --> 00:05:03,940 and so, that's what we're gonna return 97 97 00:05:03,940 --> 00:05:05,490 and so, for position zero, 98 98 00:05:05,490 --> 00:05:06,810 we're always gonna be returning 99 99 00:05:06,810 --> 00:05:08,634 what's in the one's position. 100 100 00:05:08,634 --> 00:05:13,490 So, let's say we call getDigit with position two instead, 101 101 00:05:13,490 --> 00:05:15,190 so instead of calling it with position zero, 102 102 00:05:15,190 --> 00:05:16,450 we called it with position two 103 103 00:05:16,450 --> 00:05:18,710 which would mean that we're handling the hundreds. 104 104 00:05:18,710 --> 00:05:22,820 We'd have 10 to the power of two which is 100, 105 105 00:05:22,820 --> 00:05:25,990 we divided 4725 by 100 106 106 00:05:25,990 --> 00:05:30,700 and we get 47 and then we mod 47 with 10 107 107 00:05:30,700 --> 00:05:33,890 and that would give us a remainder of seven 108 108 00:05:33,890 --> 00:05:37,010 and so, we'd return seven for the hundreds position. 109 109 00:05:37,010 --> 00:05:39,140 If we wanted the tens position, 110 110 00:05:39,140 --> 00:05:40,240 this would be one 111 111 00:05:40,240 --> 00:05:43,117 and so, we divide 4275 by 10 112 112 00:05:46,280 --> 00:05:48,210 and we get 427 113 113 00:05:48,210 --> 00:05:49,800 and then we'd mod that with 10 114 114 00:05:49,800 --> 00:05:51,400 and the remainder would be seven 115 115 00:05:51,400 --> 00:05:53,450 and so, that's how the getDigit method 116 116 00:05:53,450 --> 00:05:56,510 is figuring out what the value of the digit 117 117 00:05:56,510 --> 00:05:58,280 at each position is. 118 118 00:05:58,280 --> 00:06:01,250 So, returning back to our radixSingleSort method. 119 119 00:06:01,250 --> 00:06:04,447 For each value, we're going to get the digit 120 120 00:06:04,447 --> 00:06:06,860 at the position and on the first call 121 121 00:06:06,860 --> 00:06:08,180 that position will be zero, 122 122 00:06:08,180 --> 00:06:11,020 so we're gonna be returning all of the one positions 123 123 00:06:11,020 --> 00:06:15,340 and so, it's going to increment the countArray, 124 124 00:06:15,340 --> 00:06:18,790 it's gonna count all the values that have zero 125 125 00:06:18,790 --> 00:06:19,900 in the one's position, 126 126 00:06:19,900 --> 00:06:23,100 all the values that have one, two, three et cetera. 127 127 00:06:23,100 --> 00:06:25,340 So, by the time we finish this loop. 128 128 00:06:25,340 --> 00:06:28,540 We have a conventional countArray 129 129 00:06:28,540 --> 00:06:31,200 where all we're doing is counting the number of values 130 130 00:06:31,200 --> 00:06:35,160 that have a specific digit in their one's position. 131 131 00:06:35,160 --> 00:06:39,460 But we want this to be a stable counting sort 132 132 00:06:39,460 --> 00:06:42,350 and so, we're now going to do the step 133 133 00:06:42,350 --> 00:06:45,640 that we discussed in the slides, 134 134 00:06:45,640 --> 00:06:47,820 and we need to adjust these counts 135 135 00:06:47,820 --> 00:06:51,330 so that instead of having just raw counts 136 136 00:06:51,330 --> 00:06:53,660 of how many values, how many specific digit, 137 137 00:06:53,660 --> 00:06:56,540 we want each position in the countArray 138 138 00:06:56,540 --> 00:06:59,540 to contain how values have that digit 139 139 00:06:59,540 --> 00:07:01,710 or less than that digit 140 140 00:07:01,710 --> 00:07:03,990 and so, as I said, when we went over the slides, 141 141 00:07:03,990 --> 00:07:05,360 all we have to do to get that 142 142 00:07:05,360 --> 00:07:10,040 is sum up all of the counts up to and including the digit 143 143 00:07:10,040 --> 00:07:10,873 that we're working on, 144 144 00:07:10,873 --> 00:07:14,460 so to get the number of values that have three or less 145 145 00:07:14,460 --> 00:07:15,670 in the one's position, 146 146 00:07:15,670 --> 00:07:18,787 we have to sum up the counts in positions zero, one, 147 147 00:07:18,787 --> 00:07:21,030 two and three and so, let's do that now, 148 148 00:07:21,030 --> 00:07:24,160 so we'll say for int j equals one, 149 149 00:07:24,160 --> 00:07:26,130 we don't have to handle the first index 150 150 00:07:26,130 --> 00:07:29,259 because the number of values that have zero 151 151 00:07:29,259 --> 00:07:31,860 or less in their one's position 152 152 00:07:31,860 --> 00:07:33,760 are gonna be the number of values that have zero, 153 153 00:07:33,760 --> 00:07:35,660 so we don't have to worry about changing 154 154 00:07:35,660 --> 00:07:39,321 the first count, we just have to worry about changing 155 155 00:07:39,321 --> 00:07:42,480 the counts in positions one and beyond, 156 156 00:07:42,480 --> 00:07:44,940 so for int j equals one, 157 157 00:07:44,940 --> 00:07:46,830 j is less than the radix 158 158 00:07:46,830 --> 00:07:49,180 'cause that's the length of our countArray, j++ 159 159 00:07:53,172 --> 00:07:55,505 and we just say countArray j 160 160 00:07:58,393 --> 00:08:01,310 plus equals countArray j minus one. 161 161 00:08:03,510 --> 00:08:05,100 And so, what this loop is doing 162 162 00:08:05,100 --> 00:08:07,380 is adding up if j is three, 163 163 00:08:07,380 --> 00:08:11,230 it'll add up indices zero, one, two, and three 164 164 00:08:11,230 --> 00:08:14,340 and assign and that'll be what countArray three 165 165 00:08:14,340 --> 00:08:15,173 ends up being. 166 166 00:08:15,173 --> 00:08:16,430 If countArray is five, 167 167 00:08:16,430 --> 00:08:19,620 it'll add up indices zero, one, two, three, four and five. 168 168 00:08:19,620 --> 00:08:21,470 That's what countArray five'll end up being. 169 169 00:08:21,470 --> 00:08:24,800 So, at the end of this I'll put a comment in here, 170 170 00:08:24,800 --> 00:08:26,693 adjust the count array. 171 171 00:08:28,600 --> 00:08:30,320 And so, at the end of this loop, 172 172 00:08:30,320 --> 00:08:32,100 the countArray has been adjusted, 173 173 00:08:32,100 --> 00:08:34,210 so instead of containing raw counts, 174 174 00:08:34,210 --> 00:08:37,020 it now contains the number of values 175 175 00:08:37,020 --> 00:08:40,040 that have that digit or less than that digit 176 176 00:08:40,040 --> 00:08:42,040 in the position that we're working with. 177 177 00:08:43,670 --> 00:08:46,720 And so, at this point, we're going to do the step 178 178 00:08:46,720 --> 00:08:48,070 that we went through on the slides 179 179 00:08:48,070 --> 00:08:50,220 where we're going to copy the values 180 180 00:08:50,220 --> 00:08:52,120 into a temporary array, 181 181 00:08:52,120 --> 00:08:53,870 we're gonna work from right to left 182 182 00:08:53,870 --> 00:08:56,460 so that we're preserving the relative ordering 183 183 00:08:56,460 --> 00:08:58,450 of duplicates and so, we're gonna create 184 184 00:08:58,450 --> 00:08:59,600 that temporary array, 185 185 00:08:59,600 --> 00:09:02,980 so we'll say int temp equals 186 186 00:09:04,130 --> 00:09:07,180 new int and we need that to be enough 187 187 00:09:07,180 --> 00:09:09,270 to hold the number of items we have, 188 188 00:09:09,270 --> 00:09:10,320 so we'll say numItems 189 189 00:09:12,210 --> 00:09:17,210 and then for int tempIndex equals numItems 190 190 00:09:18,297 --> 00:09:21,583 minus one, so we're starting at the end, 191 191 00:09:22,910 --> 00:09:25,790 tempIndex greater equal to zero 192 192 00:09:27,690 --> 00:09:29,603 and we're going to decrement it. 193 193 00:09:30,850 --> 00:09:34,030 On each iteration, we're going to say temp 194 194 00:09:36,010 --> 00:09:38,240 minus minus countArray 195 195 00:09:38,240 --> 00:09:40,293 and again we're gonna use getDigit, 196 196 00:09:42,830 --> 00:09:47,497 position, input tempIndex, radix 197 197 00:09:53,550 --> 00:09:58,250 equals and this is gonna equal input tempIndex. 198 198 00:09:58,250 --> 00:09:59,810 Now, when we went through the slides, 199 199 00:09:59,810 --> 00:10:01,803 I actually called tempIndexK, 200 200 00:10:01,803 --> 00:10:04,900 so we're doing exactly, 201 201 00:10:04,900 --> 00:10:07,470 this is the exact same code we went through 202 202 00:10:07,470 --> 00:10:11,540 on the slides and so, we're working from right to left 203 203 00:10:11,540 --> 00:10:14,650 and we're looking at the countArray, 204 204 00:10:14,650 --> 00:10:18,550 we're decrementing, remember using the prefix operator, 205 205 00:10:18,550 --> 00:10:21,800 so we decrement the value at the countArray 206 206 00:10:21,800 --> 00:10:23,170 for the digit first 207 207 00:10:23,170 --> 00:10:27,320 and then we use that index to index into the temp array 208 208 00:10:27,320 --> 00:10:31,430 and we assign the value at input tempIndex, 209 209 00:10:31,430 --> 00:10:33,010 'cause that's what we're working with 210 210 00:10:33,010 --> 00:10:37,150 and tempIndex starts at the end of the input array 211 211 00:10:37,150 --> 00:10:39,170 and moves right to left. 212 212 00:10:39,170 --> 00:10:41,627 So, because we're moving right to left 213 213 00:10:41,627 --> 00:10:43,060 with the input array 214 214 00:10:43,060 --> 00:10:45,480 and because we're writing from right to left 215 215 00:10:45,480 --> 00:10:47,980 in the range of positions occupied 216 216 00:10:47,980 --> 00:10:50,170 by a specific digit, 217 217 00:10:50,170 --> 00:10:53,160 we preserve the ordering of duplicate values, 218 218 00:10:53,160 --> 00:10:55,180 so if you're confused by what this code is doing, 219 219 00:10:55,180 --> 00:10:56,340 go to the last video 220 220 00:10:56,340 --> 00:10:57,640 because we went through it there, 221 221 00:10:57,640 --> 00:11:00,400 just keep in mind that I called in the code 222 222 00:11:00,400 --> 00:11:04,460 that I showed you tempIndex and K are one and the same. 223 223 00:11:04,460 --> 00:11:07,270 So, at this point, we've copied our values 224 224 00:11:07,270 --> 00:11:08,820 into the temporary array. 225 225 00:11:08,820 --> 00:11:11,410 They're in sorted order in the temporary array, 226 226 00:11:11,410 --> 00:11:14,070 so the last thing we have to do is copy them back 227 227 00:11:14,070 --> 00:11:17,460 from the temporary array into the input array. 228 228 00:11:17,460 --> 00:11:19,440 So, we could use system.arrayCopy 229 229 00:11:19,440 --> 00:11:21,500 but let's just do it using a regular loop, 230 230 00:11:21,500 --> 00:11:25,133 so for int, let's use the tempIndex again, 231 231 00:11:25,133 --> 00:11:27,303 tempIndex equals zero, 232 232 00:11:29,157 --> 00:11:31,810 tempIndex is less than the number of items 233 233 00:11:31,810 --> 00:11:33,883 and we'll just increment it, 234 234 00:11:34,818 --> 00:11:39,818 tempIndex++, input tempIndex 235 235 00:11:43,800 --> 00:11:47,330 equals temp, tempIndex. 236 236 00:11:48,550 --> 00:11:50,620 Nothing Earth shattering going on here, 237 237 00:11:50,620 --> 00:11:52,123 just a regular old loop. 238 238 00:11:53,370 --> 00:11:55,760 And so, to recap, we do the counting, 239 239 00:11:55,760 --> 00:11:58,210 we just get the raw counts of how many values 240 240 00:11:58,210 --> 00:12:02,630 have a specific digit at the position we're working at. 241 241 00:12:02,630 --> 00:12:04,410 We then adjust those counts. 242 242 00:12:04,410 --> 00:12:06,880 As we saw in the slides in the last video, 243 243 00:12:06,880 --> 00:12:10,300 we then write the values into a temporary array 244 244 00:12:10,300 --> 00:12:12,580 as we saw in the slides in the last video 245 245 00:12:12,580 --> 00:12:15,430 and in the final step, we copy the temporary array 246 246 00:12:15,430 --> 00:12:17,720 back into the input array 247 247 00:12:17,720 --> 00:12:19,600 and then we return from this method 248 248 00:12:19,600 --> 00:12:22,870 and then we return here to radixSort, 249 249 00:12:22,870 --> 00:12:26,290 the values have been sorted based on that position. 250 250 00:12:26,290 --> 00:12:28,500 And as you can see, we're going from zero, 251 251 00:12:28,500 --> 00:12:30,790 one, two, three, four, five et cetera 252 252 00:12:30,790 --> 00:12:31,930 depending on the width, 253 253 00:12:31,930 --> 00:12:34,740 zero is the rightmost position, 254 254 00:12:34,740 --> 00:12:36,980 it's the least significant digit. 255 255 00:12:36,980 --> 00:12:40,060 That's how this getDigit method operates 256 256 00:12:40,060 --> 00:12:43,380 because it raises 10 to the position. 257 257 00:12:43,380 --> 00:12:44,790 Actually there's a mistake here. 258 258 00:12:44,790 --> 00:12:45,973 This should be radix. 259 259 00:12:47,650 --> 00:12:50,410 So, the final thing that we have left to do 260 260 00:12:50,410 --> 00:12:52,310 is to actually call this method, 261 261 00:12:52,310 --> 00:12:53,760 so we're gonna call radixSort 262 262 00:12:55,640 --> 00:12:57,880 and we're gonna pass it our radixArray, 263 263 00:12:57,880 --> 00:13:00,480 that's our input array, our radix is 10 264 264 00:13:00,480 --> 00:13:03,993 and our width is four and let's run. 265 265 00:13:08,400 --> 00:13:11,583 And we have 1330, 1594, 266 266 00:13:12,954 --> 00:13:14,593 4586, 4725, 267 267 00:13:16,746 --> 00:13:19,560 5729 and 8792. 268 268 00:13:19,560 --> 00:13:21,570 We have sorted our array 269 269 00:13:21,570 --> 00:13:23,560 and remember that the key thing here 270 270 00:13:23,560 --> 00:13:25,680 is this has to be a stable sort 271 271 00:13:25,680 --> 00:13:29,610 and so, that's why we're doing these extra steps. 272 272 00:13:29,610 --> 00:13:32,250 We need a stable counting sort here, 273 273 00:13:32,250 --> 00:13:34,630 an unstable counting sort will not work 274 274 00:13:34,630 --> 00:13:37,970 because it would undo previous sorts 275 275 00:13:37,970 --> 00:13:42,260 when we've sorted on less significant digit positions, 276 276 00:13:42,260 --> 00:13:44,170 so we've done extra work here 277 277 00:13:44,170 --> 00:13:45,940 to make our counting sort stable 278 278 00:13:45,940 --> 00:13:47,960 and because of that, our radixSort 279 279 00:13:47,960 --> 00:13:51,280 is able to sort these values. 280 280 00:13:51,280 --> 00:13:55,210 So, that's it for sorting algorithms right now. 281 281 00:13:55,210 --> 00:13:57,530 We're gonna see a few more later in the course 282 282 00:13:57,530 --> 00:13:59,810 after we've covered some more data structures 283 283 00:13:59,810 --> 00:14:01,930 because they make use of those data structures 284 284 00:14:01,930 --> 00:14:05,533 but for now that's it, so I'll see you in the next video. 24255