Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,209 --> 00:00:05,209 (lively music) (keyboard clacking) 2 2 00:00:05,640 --> 00:00:07,580 So, let's implement counting sort. 3 3 00:00:07,580 --> 00:00:09,500 Once again I've created a project, 4 4 00:00:09,500 --> 00:00:11,720 I've got the code in package 5 5 00:00:11,720 --> 00:00:14,740 academy.learnprogramming.countingsort. 6 6 00:00:14,740 --> 00:00:18,160 And I'm going to write a method called countingSort. 7 7 00:00:18,160 --> 00:00:22,563 So, I'll say public static void countingSort 8 8 00:00:23,770 --> 00:00:26,850 and we're going to accept the input array 9 9 00:00:28,220 --> 00:00:31,840 and the minimum value in the range 10 10 00:00:31,840 --> 00:00:33,860 and the maximum value in the range. 11 11 00:00:33,860 --> 00:00:36,360 Remember, that countingSort assumes 12 12 00:00:36,360 --> 00:00:40,590 that all the values fall within the range min to max. 13 13 00:00:40,590 --> 00:00:41,920 So, the first thing we're going to do 14 14 00:00:41,920 --> 00:00:44,600 is to create the counting array, 15 15 00:00:44,600 --> 00:00:46,830 the array that's going to keep track of the count, 16 16 00:00:46,830 --> 00:00:49,027 so we'll say int countArray 17 17 00:00:50,870 --> 00:00:53,250 and this array has to be large enough 18 18 00:00:53,250 --> 00:00:56,380 to be able to count each possible value 19 19 00:00:56,380 --> 00:00:58,550 and so, we're gonna say new int 20 20 00:00:58,550 --> 00:01:03,550 and we want it to be max minus min plus one in length. 21 21 00:01:05,710 --> 00:01:08,770 If our minimum is one, and our maximum is 10, 22 22 00:01:08,770 --> 00:01:11,000 which is what we're going to pass in, 23 23 00:01:11,000 --> 00:01:15,120 then we're going to create an array of length 10 24 24 00:01:15,120 --> 00:01:18,120 minus one which is nine plus one which is 10 25 25 00:01:18,120 --> 00:01:19,100 and that's what we want 26 26 00:01:19,100 --> 00:01:22,400 because we have a possible 10 values, 27 27 00:01:22,400 --> 00:01:24,340 one to 10 inclusive. 28 28 00:01:24,340 --> 00:01:26,260 So, once we've created our countArray, 29 29 00:01:26,260 --> 00:01:27,400 what do we wanna do? 30 30 00:01:27,400 --> 00:01:29,370 We want to traverse our input array 31 31 00:01:29,370 --> 00:01:31,070 and here's our input array up here, 32 32 00:01:31,070 --> 00:01:32,450 it's not our usual array, 33 33 00:01:32,450 --> 00:01:35,960 it's the aray that we went through in the slides. 34 34 00:01:35,960 --> 00:01:37,940 And so, we're gonna traverse this array 35 35 00:01:37,940 --> 00:01:41,400 and we're gonna count how many of each value we have. 36 36 00:01:41,400 --> 00:01:45,540 And so, we're gonna say for int i equals zero, 37 37 00:01:45,540 --> 00:01:47,893 i less than input.length, 38 38 00:01:49,706 --> 00:01:54,380 i++ and we're gonna say countArray 39 39 00:01:54,380 --> 00:01:57,580 and the way that we figure out 40 40 00:01:57,580 --> 00:02:00,350 where each value is counted 41 41 00:02:00,350 --> 00:02:05,243 is we say input i minus min. 42 42 00:02:08,640 --> 00:02:10,810 That's going to be the index 43 43 00:02:10,810 --> 00:02:12,530 of where to count each value. 44 44 00:02:12,530 --> 00:02:15,110 So, for example, let's say input i 45 45 00:02:15,110 --> 00:02:16,930 is equal to five, 46 46 00:02:16,930 --> 00:02:19,000 so let's say we're at the point 47 47 00:02:19,000 --> 00:02:20,760 where we're counting this one. 48 48 00:02:20,760 --> 00:02:24,140 To figure out which element we should increment 49 49 00:02:24,140 --> 00:02:28,330 in the countArray, we would say five minus one 50 50 00:02:28,330 --> 00:02:29,900 because that's our minimum 51 51 00:02:29,900 --> 00:02:32,680 and so, we'd increment count array four 52 52 00:02:32,680 --> 00:02:36,460 because remember, we could have values let's say going 53 53 00:02:36,460 --> 00:02:38,010 from 10 to 20 54 54 00:02:38,010 --> 00:02:41,690 and in that case, the countArray would be 11 elements long 55 55 00:02:41,690 --> 00:02:45,580 and so, we need to translate the values 10 to 20 56 56 00:02:45,580 --> 00:02:48,100 to indices zero to 10 57 57 00:02:48,100 --> 00:02:49,730 and that's what we're doing here 58 58 00:02:49,730 --> 00:02:53,460 and we can do that just by subtracting out the minimum 59 59 00:02:53,460 --> 00:02:55,410 from whatever value we're counting 60 60 00:02:55,410 --> 00:02:57,630 and so, to count ones, 61 61 00:02:57,630 --> 00:03:00,480 if we got a one, we'd subtract one minus one, 62 62 00:03:00,480 --> 00:03:03,230 so we'd increment element zero. 63 63 00:03:03,230 --> 00:03:06,240 If we got a two, two minus min is one 64 64 00:03:06,240 --> 00:03:09,270 and so, we'd increment element one. 65 65 00:03:09,270 --> 00:03:11,530 If we got a 10, 10 minus one is nine 66 66 00:03:11,530 --> 00:03:14,855 and we'd increment element nine in the countArray. 67 67 00:03:14,855 --> 00:03:16,660 And so, all this is doing 68 68 00:03:16,660 --> 00:03:19,800 is translating the value we wanna count 69 69 00:03:19,800 --> 00:03:21,970 into its index in the countArray. 70 70 00:03:21,970 --> 00:03:23,290 And what do we wanna do? 71 71 00:03:23,290 --> 00:03:25,370 We wanna increment that position 72 72 00:03:25,370 --> 00:03:26,830 and so, that's all we do here. 73 73 00:03:26,830 --> 00:03:29,163 So, this is the counting phase. 74 74 00:03:30,360 --> 00:03:32,100 That's all it involves. 75 75 00:03:32,100 --> 00:03:34,340 We go through each element in the array, 76 76 00:03:34,340 --> 00:03:35,700 we look at the value, 77 77 00:03:35,700 --> 00:03:38,880 we figure out where we're counting that value 78 78 00:03:38,880 --> 00:03:39,900 in the countArray 79 79 00:03:39,900 --> 00:03:42,671 and we increment that value by one. 80 80 00:03:42,671 --> 00:03:45,110 So, once we've finished counting, 81 81 00:03:45,110 --> 00:03:48,280 we now wanna write the values back into the input array, 82 82 00:03:48,280 --> 00:03:51,030 so we're gonna say int j equals zero 83 83 00:03:52,100 --> 00:03:55,750 and then for int i equals min, 84 84 00:03:55,750 --> 00:03:58,943 i less than or equal to max. 85 85 00:04:01,650 --> 00:04:03,083 I++. 86 86 00:04:05,450 --> 00:04:07,510 So, what are we doing here? 87 87 00:04:07,510 --> 00:04:09,610 J is the index we're going to use 88 88 00:04:09,610 --> 00:04:11,570 to write to the input array. 89 89 00:04:11,570 --> 00:04:14,470 And i is the index that we're going to use 90 90 00:04:14,470 --> 00:04:17,470 to traverse the countArray. 91 91 00:04:17,470 --> 00:04:18,860 We're setting i to min 92 92 00:04:18,860 --> 00:04:20,480 and i less than or equal to max 93 93 00:04:20,480 --> 00:04:21,940 because as you'll see, 94 94 00:04:21,940 --> 00:04:23,390 because we're doing it this way, 95 95 00:04:23,390 --> 00:04:26,690 we can just write the value of i back 96 96 00:04:26,690 --> 00:04:29,120 to the input array on each iteration. 97 97 00:04:29,120 --> 00:04:31,820 So, inside the loop, we're gonna say while countArray 98 98 00:04:33,980 --> 00:04:35,440 i minus min 99 99 00:04:36,870 --> 00:04:39,763 is greater than zero. 100 100 00:04:41,640 --> 00:04:42,900 And you'll see why in a minute. 101 101 00:04:42,900 --> 00:04:44,240 Let me write the rest of the code. 102 102 00:04:44,240 --> 00:04:47,717 So, we'll say input j++ equals i 103 103 00:04:49,640 --> 00:04:54,640 and countArray i minus min minus minus. 104 104 00:04:59,470 --> 00:05:01,210 So, what's going on here? 105 105 00:05:01,210 --> 00:05:02,360 What we're doing here 106 106 00:05:02,360 --> 00:05:05,690 is remember that each element in the countArray 107 107 00:05:05,690 --> 00:05:08,740 has a count and that count can be greater than one. 108 108 00:05:08,740 --> 00:05:11,490 So, let's go through this for the number of twos 109 109 00:05:11,490 --> 00:05:14,340 because we know we have two twos in our array 110 110 00:05:14,340 --> 00:05:18,500 and the count of twos is kept in countArray one. 111 111 00:05:18,500 --> 00:05:20,150 So, when i is two, 112 112 00:05:20,150 --> 00:05:22,660 we say while countArray two minus one 113 113 00:05:22,660 --> 00:05:25,480 which is countArray one is greater than zero, 114 114 00:05:25,480 --> 00:05:28,350 we wanna keep writing twos to the input array 115 115 00:05:28,350 --> 00:05:30,900 because at this point, we're writing the number of twos. 116 116 00:05:30,900 --> 00:05:32,750 And so, the first thing we do 117 117 00:05:32,750 --> 00:05:35,380 is we write a two 118 118 00:05:35,380 --> 00:05:36,960 to the input array 119 119 00:05:36,960 --> 00:05:39,070 and then we need to decrement the count. 120 120 00:05:39,070 --> 00:05:40,980 We've already written one two 121 121 00:05:40,980 --> 00:05:43,850 and so, we only have another two left to write 122 122 00:05:43,850 --> 00:05:47,690 and so, we started with countArray one equals two 123 123 00:05:47,690 --> 00:05:49,640 because we have two twos, 124 124 00:05:49,640 --> 00:05:51,930 we write one of the twos to the input array 125 125 00:05:51,930 --> 00:05:53,860 and then we decrement the count to one 126 126 00:05:53,860 --> 00:05:57,500 because we only have one two remaining. 127 127 00:05:57,500 --> 00:06:01,750 We loop around, countArray one is still greater than zero, 128 128 00:06:01,750 --> 00:06:03,790 so we're gonna write another two 129 129 00:06:03,790 --> 00:06:06,000 and then we're gonna decrement the count again 130 130 00:06:06,000 --> 00:06:07,610 and at this point, the count will be zero 131 131 00:06:07,610 --> 00:06:09,430 because we've written both of the twos 132 132 00:06:09,430 --> 00:06:10,940 back to the input array 133 133 00:06:10,940 --> 00:06:13,020 and so, when we loop back around, 134 134 00:06:13,020 --> 00:06:15,530 at this point countArray one will be equal to zero 135 135 00:06:15,530 --> 00:06:16,890 and we drop out of the loop 136 136 00:06:16,890 --> 00:06:19,260 and then i will be incremented to three 137 137 00:06:19,260 --> 00:06:22,480 and we enter this loop to write the number of threes 138 138 00:06:22,480 --> 00:06:25,590 and once again, each time we write a three, 139 139 00:06:25,590 --> 00:06:27,000 I don't believe we have any, 140 140 00:06:27,000 --> 00:06:30,100 we do, one at the end, so each time we write a three, 141 141 00:06:30,100 --> 00:06:31,900 the count will be decremented by one 142 142 00:06:31,900 --> 00:06:33,260 until we've written all the threes 143 143 00:06:33,260 --> 00:06:35,680 and then we'll loop around and we'll write the fours. 144 144 00:06:35,680 --> 00:06:37,280 So, we've written the loop this way 145 145 00:06:37,280 --> 00:06:39,780 starting i at min because then we can just 146 146 00:06:39,780 --> 00:06:41,880 when we're writing out the number of ones, 147 147 00:06:41,880 --> 00:06:42,750 i will be one, 148 148 00:06:42,750 --> 00:06:44,980 when we're writing out the number of twos, i will be two. 149 149 00:06:44,980 --> 00:06:47,660 So, we can just stick i in 150 150 00:06:47,660 --> 00:06:49,700 and subtract here. 151 151 00:06:49,700 --> 00:06:51,660 We could have started i at zero 152 152 00:06:51,660 --> 00:06:53,200 but then we'd need to do a different type 153 153 00:06:53,200 --> 00:06:54,770 of calculation here. 154 154 00:06:54,770 --> 00:06:57,630 We'd need to figure out what value we're writing. 155 155 00:06:57,630 --> 00:07:00,420 So, I think it's clear to set i to min 156 156 00:07:00,420 --> 00:07:04,150 because then we know that on the first iteration 157 157 00:07:04,150 --> 00:07:05,310 we're writing out one, 158 158 00:07:05,310 --> 00:07:07,170 the second iteration we're writing the twos, 159 159 00:07:07,170 --> 00:07:09,810 the third iteration we're writing the threes et cetera. 160 160 00:07:09,810 --> 00:07:11,790 And of course j is keeping track 161 161 00:07:11,790 --> 00:07:13,760 of where we are in the input array. 162 162 00:07:13,760 --> 00:07:17,790 So, this is a fairly straightforward algorithm I would say. 163 163 00:07:17,790 --> 00:07:19,410 If you're having trouble understanding it, 164 164 00:07:19,410 --> 00:07:21,330 you can go and check the slides 165 165 00:07:21,330 --> 00:07:23,160 but of course we wanna see if it works, 166 166 00:07:23,160 --> 00:07:25,683 so let's call countingSort 167 167 00:07:27,260 --> 00:07:28,860 and we'll call it with intArray, 168 168 00:07:30,451 --> 00:07:31,780 our minimum value is one, 169 169 00:07:31,780 --> 00:07:34,140 and our maximum value is 10, 170 170 00:07:34,140 --> 00:07:35,783 so let's go ahead and run. 171 171 00:07:40,920 --> 00:07:42,510 And here we go. 172 172 00:07:42,510 --> 00:07:45,420 Two, two, three, four, five, 173 173 00:07:45,420 --> 00:07:48,240 seven, eight, eight, nine and 10. 174 174 00:07:48,240 --> 00:07:49,984 Exactly what we expect. 175 175 00:07:49,984 --> 00:07:52,770 And so, that's countingSort 176 176 00:07:52,770 --> 00:07:54,820 and once again, this algorithm 177 177 00:07:54,820 --> 00:07:58,650 is only good to use under specific circumstances. 178 178 00:07:58,650 --> 00:08:01,070 You only wanna use it when the range 179 179 00:08:01,070 --> 00:08:02,560 of values is reasonable, 180 180 00:08:02,560 --> 00:08:04,120 meaning it's not too large 181 181 00:08:04,120 --> 00:08:08,350 and the dataset is a reasonable size as well. 182 182 00:08:08,350 --> 00:08:11,050 So, ideally the number of unique values 183 183 00:08:11,050 --> 00:08:13,839 or the range won't be significantly greater 184 184 00:08:13,839 --> 00:08:16,010 than the number items you wanna sort. 185 185 00:08:16,010 --> 00:08:17,410 So, as I said earlier, 186 186 00:08:17,410 --> 00:08:19,140 if you have an array of length 10 187 187 00:08:19,140 --> 00:08:22,000 and it can hold values from one to a million, 188 188 00:08:22,000 --> 00:08:24,430 that's not a good candidate for counting sort 189 189 00:08:24,430 --> 00:08:26,710 because you're gonna have to create a counting array 190 190 00:08:26,710 --> 00:08:29,280 of length a million to sort 10 items 191 191 00:08:29,280 --> 00:08:32,130 and obviously that wouldn't be a very good idea. 192 192 00:08:32,130 --> 00:08:33,713 I'll see you in the next video. 16018