1 00:00:00,620 --> 00:00:01,640 Welcome back. 2 00:00:01,640 --> 00:00:06,410 Let's now go ahead and implement the radix sort, which we discussed in the previous video. 3 00:00:06,410 --> 00:00:08,180 For this we are going to write a function. 4 00:00:08,180 --> 00:00:11,270 And let's call this function radix sort itself. 5 00:00:11,270 --> 00:00:15,740 Now this function is going to take in the array of integers which is given to us. 6 00:00:15,740 --> 00:00:19,670 So remember this array over here consists only of positive integers. 7 00:00:19,670 --> 00:00:25,040 Now if you have to do radix sort on an array of integers where negative numbers are also there, we 8 00:00:25,040 --> 00:00:26,600 have to do it in a different way. 9 00:00:26,600 --> 00:00:29,870 So over here in the question it's mentioned that the integers are positive. 10 00:00:29,870 --> 00:00:30,950 Now let's go ahead. 11 00:00:30,950 --> 00:00:33,830 Now first let's check if the array is empty. 12 00:00:33,830 --> 00:00:37,640 So if array dot length is equal to zero then we can just return. 13 00:00:37,640 --> 00:00:40,760 And let's say we return a message saying the array is empty. 14 00:00:42,680 --> 00:00:43,040 All right. 15 00:00:43,070 --> 00:00:45,800 Now, if this is not the case, let's proceed further. 16 00:00:45,800 --> 00:00:53,330 So we have to first identify what is the maximum number of digits which is present in any integer which 17 00:00:53,330 --> 00:00:54,650 is given to us in the array. 18 00:00:54,680 --> 00:00:57,710 So for this let's first identify the greatest number. 19 00:00:57,710 --> 00:01:05,000 So we can say const greatest number in the array which is given to us is equal to math dot max. 20 00:01:05,680 --> 00:01:08,800 And then we will use the spread operator array. 21 00:01:08,830 --> 00:01:12,760 So this will give us the greatest number in the array which is given to us. 22 00:01:12,760 --> 00:01:17,500 Now let's go ahead and find the number of digits in the greatest number. 23 00:01:17,500 --> 00:01:21,880 Now let's have a quick side note over here and let's see how we can implement this. 24 00:01:21,880 --> 00:01:23,500 So let me grab a pen for this. 25 00:01:24,070 --> 00:01:24,520 All right. 26 00:01:24,520 --> 00:01:25,420 So we are back. 27 00:01:25,420 --> 00:01:31,450 So let me just show you the logic that we will use to find the number of digits in the greatest number 28 00:01:31,450 --> 00:01:32,950 which we have identified over here. 29 00:01:32,950 --> 00:01:39,880 Now if we take a, a number and then if you take the log to the base ten for that number. 30 00:01:39,880 --> 00:01:43,480 So let's say log of a number, let's say 100. 31 00:01:43,480 --> 00:01:45,130 And this is to the base ten. 32 00:01:45,130 --> 00:01:51,190 Now typically whenever we have seen log so far in the course and even in the remaining videos, we will 33 00:01:51,190 --> 00:01:52,870 be doing log to the base two. 34 00:01:52,900 --> 00:01:58,150 Now over here, just because we have to find the number of digits we will be using, log to the base 35 00:01:58,150 --> 00:01:58,480 ten. 36 00:01:58,480 --> 00:02:02,260 So log to the base ten of 100 will be equal to two. 37 00:02:02,290 --> 00:02:04,870 Again, remember the definition of this is just the same. 38 00:02:04,870 --> 00:02:10,870 This to two over here is actually ten, which is the base to what power will give this 100 over here, 39 00:02:10,870 --> 00:02:12,190 which is equal to two. 40 00:02:12,220 --> 00:02:13,690 Now log 100. 41 00:02:13,690 --> 00:02:15,820 When we take to the base ten will be equal to two. 42 00:02:15,820 --> 00:02:22,960 Similarly log ten to the base ten will be equal to one because ten to the power one is equal to ten. 43 00:02:22,960 --> 00:02:25,780 And if you take log 1000 to the base. 44 00:02:26,770 --> 00:02:32,080 Then you will get the value as three, because ten to the power three is equal to this thousand over 45 00:02:32,080 --> 00:02:32,410 here. 46 00:02:32,440 --> 00:02:35,560 Now we will use this property to find the number of digits. 47 00:02:35,560 --> 00:02:36,910 So let's take a look. 48 00:02:36,910 --> 00:02:40,330 Now if you take any number let's say you have the number two three, four. 49 00:02:40,330 --> 00:02:43,480 And you want to know how many digits are there in this number. 50 00:02:43,480 --> 00:02:51,580 So if you take log 234 to the base ten we will get a value which is in between 2 and 3. 51 00:02:51,580 --> 00:02:57,760 Because you can see that for log 100 the value is two and log for log 1000 the value is three. 52 00:02:57,760 --> 00:03:00,640 So whatever we are getting over here is going to be some decimal. 53 00:03:00,640 --> 00:03:02,830 So it's going to be two point something. 54 00:03:02,830 --> 00:03:03,400 All right. 55 00:03:03,400 --> 00:03:08,200 So if we take this value and if we floor this so we will get two right. 56 00:03:08,200 --> 00:03:10,600 So if we floor this we will just get two. 57 00:03:10,600 --> 00:03:13,030 And then we just have to add one to it. 58 00:03:13,030 --> 00:03:16,390 And you can see that we are getting three which is the number of digits over here. 59 00:03:16,390 --> 00:03:19,030 So this is how we will find the number of digits. 60 00:03:19,030 --> 00:03:21,820 So let's just quickly see this one more time. 61 00:03:21,820 --> 00:03:26,740 So what we are going to do is let's say the greatest number is 1746. 62 00:03:26,740 --> 00:03:29,140 In the array of integers which is given to us. 63 00:03:29,140 --> 00:03:33,910 So we will find the log of this number to the base ten. 64 00:03:33,910 --> 00:03:34,420 All right. 65 00:03:34,420 --> 00:03:38,590 Now the interesting thing to notice is that for log 1000. 66 00:03:39,210 --> 00:03:44,220 To the base ten, the value is equal to three, and for log 10,000. 67 00:03:45,570 --> 00:03:46,380 To the base ten. 68 00:03:46,380 --> 00:03:47,700 The value is going to be four. 69 00:03:47,700 --> 00:03:51,540 Now 1007 46 is between 1000 and 10,000. 70 00:03:51,540 --> 00:03:55,170 So this value over here is going to be three point something. 71 00:03:55,170 --> 00:03:56,370 So it's going to be a decimal. 72 00:03:56,370 --> 00:03:57,930 So we are going to floor this. 73 00:03:57,930 --> 00:04:00,690 So when we floor this we will get the value three. 74 00:04:00,690 --> 00:04:05,610 And then we will add one to it to get the number of digits which is four over here. 75 00:04:05,610 --> 00:04:08,340 So let's go ahead and implement this in the code. 76 00:04:09,670 --> 00:04:10,090 All right. 77 00:04:10,090 --> 00:04:13,810 So we can say const number of digits. 78 00:04:16,940 --> 00:04:20,990 Is equal to math dot floor. 79 00:04:21,670 --> 00:04:27,460 And then inside this we're going to take the logarithm of the greatest number to the base ten. 80 00:04:27,460 --> 00:04:31,570 So we can say math dot log to the base ten. 81 00:04:33,480 --> 00:04:36,930 Of the greatest number, which is what we have found over here. 82 00:04:37,680 --> 00:04:38,130 All right. 83 00:04:38,130 --> 00:04:42,990 So we are taking the logarithm of the greatest number to the base ten. 84 00:04:42,990 --> 00:04:44,490 And then we are flooring it. 85 00:04:44,490 --> 00:04:46,800 And then we just have to add one to it. 86 00:04:46,800 --> 00:04:50,820 So this will give us the number of digits in the greatest number. 87 00:04:50,820 --> 00:04:54,090 So this is the number of times that we have to do the counting sort. 88 00:04:54,090 --> 00:04:55,680 So let's just write a comment over here. 89 00:04:55,680 --> 00:04:57,510 So the counting sort. 90 00:04:58,860 --> 00:05:00,030 Has to be done. 91 00:05:02,830 --> 00:05:04,780 X number of times. 92 00:05:06,500 --> 00:05:12,260 Where x is equal to the number of digits which we just now found. 93 00:05:12,260 --> 00:05:14,330 So this is now what we have to implement. 94 00:05:14,330 --> 00:05:15,260 So let's go ahead. 95 00:05:15,260 --> 00:05:21,920 So let's say for let I is equal to zero I less than number of digits. 96 00:05:22,560 --> 00:05:23,730 I plus, plus. 97 00:05:26,550 --> 00:05:27,000 All right. 98 00:05:27,000 --> 00:05:31,350 And inside this for loop we are going to call the counting sort function, which we have to go ahead 99 00:05:31,350 --> 00:05:31,860 and write. 100 00:05:31,860 --> 00:05:34,530 So we can say counting sort. 101 00:05:34,530 --> 00:05:41,790 And we will just pass in the array and we will pass in I to know at what place or whether we are we 102 00:05:41,790 --> 00:05:47,430 are doing the counting sort for the ones digits, the tens digits or the hundreds digits, etc. so that's 103 00:05:47,430 --> 00:05:48,240 why we have to pass. 104 00:05:48,240 --> 00:05:53,820 I also and then once this is done, we can just return the array and that would be the sorted array. 105 00:05:53,820 --> 00:05:55,410 So this is how we will implement this. 106 00:05:55,410 --> 00:05:59,190 Now let's go ahead and write the counting sort function which we are calling over here. 107 00:05:59,190 --> 00:06:03,510 So we can say function or let's say const. 108 00:06:05,050 --> 00:06:06,190 Counting sort. 109 00:06:08,370 --> 00:06:10,080 Is equal to function. 110 00:06:11,610 --> 00:06:13,710 And this takes in the array. 111 00:06:14,450 --> 00:06:20,240 And let's say we call the second, uh, parameter over here place to because it indicates whether we 112 00:06:20,240 --> 00:06:24,260 are doing counting sort on the ones place or the tens place, etc.. 113 00:06:24,260 --> 00:06:24,860 All right. 114 00:06:24,860 --> 00:06:25,820 So let's go ahead. 115 00:06:25,820 --> 00:06:27,830 Now first let's have an output array. 116 00:06:27,830 --> 00:06:29,570 We can say const output. 117 00:06:30,420 --> 00:06:32,370 Is equal to new array. 118 00:06:34,820 --> 00:06:39,800 And this array is going to be of length equal to the length of the array which is given to us. 119 00:06:39,800 --> 00:06:41,240 So that's array dot length. 120 00:06:41,810 --> 00:06:45,650 And then let's just fill every value in this output array with zero. 121 00:06:45,710 --> 00:06:47,120 So fill zero. 122 00:06:52,110 --> 00:06:58,740 Now let's go ahead and have a temporary array where we will count the number of times that each digit 123 00:06:58,740 --> 00:06:59,280 occurs. 124 00:06:59,280 --> 00:07:04,320 And remember, every digit is going to be between 0 and 9 because this is the decimal system. 125 00:07:04,320 --> 00:07:08,280 So we have const temp and there are only ten possible values. 126 00:07:08,280 --> 00:07:11,520 So this array is going to be of length ten right. 127 00:07:11,520 --> 00:07:14,310 Because the possible values are 0 to 9. 128 00:07:14,310 --> 00:07:16,800 So new array of length ten. 129 00:07:18,060 --> 00:07:21,900 And let's just fill every place in this array also with zero. 130 00:07:24,090 --> 00:07:27,720 Now let's go ahead and identify the digit place. 131 00:07:27,720 --> 00:07:31,380 So let's have a side note and understand what we're trying to do over here. 132 00:07:32,520 --> 00:07:38,970 We are going to identify a method by which we can just isolate the digit that we need from the integer. 133 00:07:39,000 --> 00:07:39,450 All right. 134 00:07:39,450 --> 00:07:42,570 So again this array is going to have the various integers. 135 00:07:42,570 --> 00:07:45,330 Now let's say one of the integers is 241. 136 00:07:45,360 --> 00:07:52,680 Now when we are implementing counting sort on the ones place, we will only want the digit one. 137 00:07:52,680 --> 00:07:58,650 Right now, when we are implementing the counting sort on the tens place, we will only want the digit 138 00:07:58,650 --> 00:07:59,100 four. 139 00:07:59,100 --> 00:08:04,560 And similarly, when we are implementing the counting sort on the hundreds place, we will only want 140 00:08:04,560 --> 00:08:05,280 the digit two. 141 00:08:05,310 --> 00:08:06,930 So let's see how we can do this. 142 00:08:06,930 --> 00:08:10,830 Now for this, let's say first we want the units place which is one. 143 00:08:10,830 --> 00:08:13,920 So what we will do is let me just change the color of the pin. 144 00:08:13,920 --> 00:08:20,730 So what we will do is we will do 241 and then we will just take the mod of ten of this. 145 00:08:20,730 --> 00:08:20,970 All right. 146 00:08:20,970 --> 00:08:25,080 So that means we will divide 241 with ten and take the remainder. 147 00:08:25,080 --> 00:08:30,540 So 241 divided by ten gives the remainder remainder as one which is this digit over here. 148 00:08:30,540 --> 00:08:32,370 So that's how we will get one. 149 00:08:32,370 --> 00:08:33,930 Now let's say we want four. 150 00:08:33,930 --> 00:08:35,520 So let's see what we can do. 151 00:08:35,520 --> 00:08:41,880 So first what we will do is we will take 241 and we will divide 241 with ten. 152 00:08:42,300 --> 00:08:46,320 So when we divide two 241 with ten and then we are flooring it. 153 00:08:48,530 --> 00:08:51,020 When we do this, we will get 24. 154 00:08:51,700 --> 00:08:54,340 Now on 24, we will do the same thing. 155 00:08:54,340 --> 00:08:56,230 That is, we will take mod of ten. 156 00:08:56,230 --> 00:08:56,620 All right. 157 00:08:56,620 --> 00:09:02,080 So this will give us the remainder when 24 is divided by ten which is equal to four. 158 00:09:02,650 --> 00:09:08,620 And similarly when we want to in this case what we will do is we will take 241 and we will divide it 159 00:09:08,620 --> 00:09:09,550 with 100. 160 00:09:09,550 --> 00:09:09,820 All right. 161 00:09:09,820 --> 00:09:11,230 So in this case it was ten. 162 00:09:11,230 --> 00:09:12,970 Over here we are dividing it with 100. 163 00:09:12,970 --> 00:09:14,440 And then we will floor it. 164 00:09:15,900 --> 00:09:21,570 So when we do 241 divided by 100 and then when you're flooring it, we will get two, and then we will 165 00:09:21,570 --> 00:09:22,410 just do the same thing. 166 00:09:22,410 --> 00:09:24,360 That is we are going to do percentage ten. 167 00:09:24,750 --> 00:09:29,850 And this will give us the remainder when two is divided by ten which is two itself. 168 00:09:29,850 --> 00:09:32,100 And that's how we will get this digit right. 169 00:09:32,100 --> 00:09:34,200 So this is what we are going to implement. 170 00:09:34,200 --> 00:09:37,770 Now notice that percentage ten is the same across right. 171 00:09:37,770 --> 00:09:40,200 So over here also we have percentage ten over here. 172 00:09:40,200 --> 00:09:41,550 Also we have percentage ten. 173 00:09:41,550 --> 00:09:43,470 And over here also we have the same thing. 174 00:09:43,470 --> 00:09:45,030 So we are using the modulo operator. 175 00:09:45,030 --> 00:09:51,120 Now what is changing is in this case 241 is divided with ten to the power zero. 176 00:09:52,370 --> 00:09:53,420 Which is one. 177 00:09:53,420 --> 00:09:59,480 In this case, we are dividing 241 with ten to the power one, and in this case we are dividing 241 178 00:09:59,480 --> 00:10:01,730 with ten to the power two, which is 100. 179 00:10:01,730 --> 00:10:02,120 Right. 180 00:10:02,120 --> 00:10:06,770 And again, notice over here, when we are calling the counting sort function, let's say the number 181 00:10:06,770 --> 00:10:08,750 of digits is maximum three. 182 00:10:08,750 --> 00:10:12,650 So the values that I will take is zero one and two. 183 00:10:12,650 --> 00:10:14,390 And we are passing these values also. 184 00:10:14,390 --> 00:10:19,970 So when we want the units digit we just have to raise ten to the power zero which is I itself. 185 00:10:19,970 --> 00:10:24,290 When we want the 10th digit we have to just raise ten to the power I, which is one. 186 00:10:24,290 --> 00:10:28,670 And similarly, when we want the hundredths digit we have to raise for the denominator, I'm saying 187 00:10:28,670 --> 00:10:32,450 we have to just raise ten to the power two, which is also the value of I. 188 00:10:32,480 --> 00:10:35,060 So let's go ahead and implement this in our code. 189 00:10:35,060 --> 00:10:40,730 And so again remember this is to get the particular digit that we need because we are implementing the 190 00:10:40,730 --> 00:10:46,490 counting sort first on the units digits and then on the tenths digits and then on the hundredths digits 191 00:10:46,490 --> 00:10:47,240 and etc.. 192 00:10:47,240 --> 00:10:49,340 So let's go ahead and implement this now. 193 00:10:49,790 --> 00:10:50,240 All right. 194 00:10:50,270 --> 00:10:54,560 Now to know by what I have to divide the particular integer. 195 00:10:54,560 --> 00:10:57,230 Let's have a variable. 196 00:10:57,230 --> 00:10:59,210 Let's call it digit place. 197 00:11:00,980 --> 00:11:06,590 Because that will depend on what place or whether it's once digits or tens, digits or hundreds, digits, 198 00:11:06,590 --> 00:11:07,910 etc. that we are sorting. 199 00:11:07,910 --> 00:11:10,310 So that's why I'm calling it digits place over here. 200 00:11:10,310 --> 00:11:11,450 Now let's proceed. 201 00:11:11,450 --> 00:11:13,760 So we have digits place over here. 202 00:11:13,760 --> 00:11:18,650 And again remember when I was equal to zero we had to divide by ten to the power zero. 203 00:11:18,650 --> 00:11:22,070 When I was equal to one we had to divide by ten to the power one. 204 00:11:22,070 --> 00:11:25,310 So digit place is just going to be math dot pow. 205 00:11:26,270 --> 00:11:27,860 Ten comma AI. 206 00:11:28,340 --> 00:11:30,680 That means we are going to raise ten to the power I. 207 00:11:30,710 --> 00:11:34,220 Now when we are sorting the units place, I is going to be zero. 208 00:11:34,220 --> 00:11:37,790 And when we are sorting the tens place, I is going to be one, etc.. 209 00:11:37,790 --> 00:11:39,770 So we get the digit place over here. 210 00:11:39,770 --> 00:11:48,020 Now what we will do is let's go ahead and loop through the numbers in our array and let's, uh, fill 211 00:11:48,020 --> 00:11:50,930 out what the frequency of the digits is. 212 00:11:50,930 --> 00:11:53,540 And accordingly we are going to change the temp array. 213 00:11:53,540 --> 00:11:55,880 So we have discussed this in the concept video. 214 00:11:56,360 --> 00:12:00,470 So let's go ahead and uh get the correct frequencies into the temp array. 215 00:12:00,470 --> 00:12:05,780 So for this let's say for let num of array. 216 00:12:07,080 --> 00:12:12,150 So we are taking each integer at a time, and then we are going to find the respective digit. 217 00:12:12,150 --> 00:12:17,310 So let's say let digit is equal to math dot floor. 218 00:12:18,370 --> 00:12:22,930 And then we are doing numb divided by digit place. 219 00:12:25,180 --> 00:12:25,780 All right. 220 00:12:25,780 --> 00:12:31,510 And after doing this, after doing the division and then after flooring this, what we will do is we 221 00:12:31,510 --> 00:12:33,340 will just take percentage of ten. 222 00:12:34,120 --> 00:12:35,200 Or modulo ten. 223 00:12:35,200 --> 00:12:35,560 Right. 224 00:12:35,560 --> 00:12:36,850 So we are getting the remainder. 225 00:12:36,850 --> 00:12:38,680 So this is how we are going about with this. 226 00:12:38,680 --> 00:12:40,900 So we do num divided by digit place. 227 00:12:40,900 --> 00:12:44,500 And then we floor it and then we take percentage ten. 228 00:12:44,500 --> 00:12:46,030 So that's what we just now discussed. 229 00:12:46,030 --> 00:12:48,130 So this will give us the particular digit. 230 00:12:48,130 --> 00:12:55,360 So again remember if the number is 241 for example when we are sorting the units digits this will give 231 00:12:55,360 --> 00:12:56,080 us one. 232 00:12:56,080 --> 00:12:59,890 When we are sorting the sorting according to the tenths digits. 233 00:12:59,890 --> 00:13:02,470 This operation over here will give us four, etc.. 234 00:13:02,470 --> 00:13:04,210 So that is what we have done over here. 235 00:13:04,210 --> 00:13:05,470 Now let's proceed. 236 00:13:05,470 --> 00:13:06,640 Now we know the digit. 237 00:13:06,670 --> 00:13:12,910 Now we are going to increase the count in the temp array at the digit index at index equal to digit. 238 00:13:12,910 --> 00:13:15,190 So we can say temp at digit. 239 00:13:16,350 --> 00:13:17,100 Plus plus. 240 00:13:18,120 --> 00:13:18,510 All right. 241 00:13:18,510 --> 00:13:20,520 So this will give us the array. 242 00:13:20,610 --> 00:13:24,600 And now what we have to do is we have to take the cumulative sum for this. 243 00:13:24,600 --> 00:13:24,870 Right. 244 00:13:24,870 --> 00:13:26,040 So let's go ahead and do that. 245 00:13:26,040 --> 00:13:28,980 So for let I is equal to zero. 246 00:13:29,970 --> 00:13:38,910 I less than ten I plus plus and oh here we have ten because our temp array is of size ten right. 247 00:13:38,910 --> 00:13:43,710 Only values from 0 to 9 can be there over here because this is in decimal system. 248 00:13:43,710 --> 00:13:50,220 And then we just say temp at I is going to be equal to temp at I. 249 00:13:52,810 --> 00:13:54,400 Temp at I minus one. 250 00:13:56,020 --> 00:13:56,260 All right. 251 00:13:56,260 --> 00:13:59,560 So this will give us the cumulative sum in the temp array. 252 00:13:59,860 --> 00:14:04,720 And now we just have to go ahead and go from in the reverse direction. 253 00:14:04,720 --> 00:14:04,870 Right. 254 00:14:04,870 --> 00:14:07,720 So we have seen that we have to go and in the reverse direction. 255 00:14:07,720 --> 00:14:11,950 So we will loop through the array which is given to us in the reverse direction. 256 00:14:11,950 --> 00:14:19,210 And then we will find the digit based on whether we are sorting based on one digit, etc. we will take 257 00:14:19,210 --> 00:14:26,440 the digit, and then we will decrement the count in the temp array for that particular index and take 258 00:14:26,440 --> 00:14:28,330 the value after decrementing it. 259 00:14:28,330 --> 00:14:30,160 So that's going to be the insert position. 260 00:14:30,160 --> 00:14:35,950 And at that position in the output array we will insert the value which is there in the array which 261 00:14:35,950 --> 00:14:36,610 is given to us. 262 00:14:36,610 --> 00:14:38,200 So that's how we're going to implement this. 263 00:14:38,200 --> 00:14:40,180 So let's go ahead and write this in code. 264 00:14:40,180 --> 00:14:43,450 And again remember this is what we discussed in the concept video. 265 00:14:43,450 --> 00:14:47,620 So if you feel confused with this do try to see that one more time. 266 00:14:47,620 --> 00:14:49,240 Now let's go ahead and implement this. 267 00:14:49,240 --> 00:14:51,550 So we're going from the back to the front. 268 00:14:51,550 --> 00:14:56,470 So let J equal to array dot length minus one which is the last index. 269 00:14:57,760 --> 00:15:01,750 And this will keep looping as long as j greater than equal to zero. 270 00:15:01,750 --> 00:15:03,610 And then we do j minus minus. 271 00:15:04,450 --> 00:15:09,250 Now once inside the for loop what we will do is first we have to find the current digit. 272 00:15:09,250 --> 00:15:10,450 So let's say current digit. 273 00:15:10,450 --> 00:15:12,580 So we have a variable. 274 00:15:12,730 --> 00:15:16,420 Now this is going to be equal to math dot floor. 275 00:15:18,360 --> 00:15:20,490 Aria j, which is the value. 276 00:15:22,420 --> 00:15:24,400 Divided by digit place. 277 00:15:29,640 --> 00:15:32,100 And then we are just going to take percentage ten. 278 00:15:33,210 --> 00:15:34,380 Alright, so it's the same thing. 279 00:15:34,380 --> 00:15:40,650 So we are taking the integer and then we are dividing it with digit place and we are floating it. 280 00:15:40,680 --> 00:15:41,100 All right. 281 00:15:41,100 --> 00:15:43,800 And once we have floated it we are going to take percentage ten. 282 00:15:43,800 --> 00:15:45,990 So that will give us the respective digit. 283 00:15:45,990 --> 00:15:51,810 Again it the digit that we want will depend on whether we are sorting based on the ones digit or the 284 00:15:51,810 --> 00:15:54,330 tens digits or the hundredths digits, etc.. 285 00:15:54,330 --> 00:16:00,870 So once we get the digit, we are going to decrement the value in the temp array at index current digit. 286 00:16:01,530 --> 00:16:03,990 So temp at current digit minus minus. 287 00:16:03,990 --> 00:16:08,190 Now we have some value in the temp array at digit. 288 00:16:08,190 --> 00:16:14,700 So that is going to be the index in the output array where we want to insert the value that is array 289 00:16:14,700 --> 00:16:15,060 at j. 290 00:16:15,060 --> 00:16:18,690 So let's just have one more variable to make the code more readable. 291 00:16:18,690 --> 00:16:21,120 So let's say let insert position. 292 00:16:23,590 --> 00:16:27,700 Is equal to temp at current digit. 293 00:16:27,700 --> 00:16:32,770 So this is going to be the position where we want to insert the value in the output array. 294 00:16:32,770 --> 00:16:34,810 So again we can use const over here. 295 00:16:36,280 --> 00:16:38,410 And over here also we can use const. 296 00:16:41,590 --> 00:16:48,370 Now, once we have identified the insert position, let's just say output at insert position. 297 00:16:49,100 --> 00:16:50,990 Is equal to area J. 298 00:16:53,490 --> 00:16:54,300 And that's it. 299 00:16:54,300 --> 00:16:54,750 All right. 300 00:16:54,750 --> 00:16:55,770 So that's it. 301 00:16:55,770 --> 00:17:03,270 So by by this we will have completed the counting sort for the ones digit or hundredths digits or 10th 302 00:17:03,270 --> 00:17:05,430 digit whatever based on one call. 303 00:17:05,430 --> 00:17:05,580 Right. 304 00:17:05,580 --> 00:17:11,640 So we are going to call this function the number of times x x number of times where x is equal to the 305 00:17:11,640 --> 00:17:12,540 number of digits. 306 00:17:12,540 --> 00:17:18,240 So in one time we are going to sort it either once based on one's digit or ten's digits or hundredths, 307 00:17:18,240 --> 00:17:19,170 digits, etc.. 308 00:17:19,170 --> 00:17:19,980 So that's it. 309 00:17:19,980 --> 00:17:25,680 Now all we have to do is we have to loop through the output array, and then we have to change the array 310 00:17:25,680 --> 00:17:30,540 which is given to us so that the output array is copied into the array which is given to us. 311 00:17:30,540 --> 00:17:31,500 So let's go ahead and do that. 312 00:17:31,500 --> 00:17:38,460 So for let's say for let again I is equal to zero I less than output dot length. 313 00:17:41,050 --> 00:17:42,340 I plus plus. 314 00:17:43,210 --> 00:17:49,360 And then we can just say array at I is equal to output. 315 00:17:50,300 --> 00:17:53,270 At I and that's it. 316 00:17:53,270 --> 00:17:53,720 All right. 317 00:17:53,720 --> 00:18:00,800 So this will keep this will modify the array so that the, the the order changes as per the output that 318 00:18:00,800 --> 00:18:02,660 we have built over here the output array. 319 00:18:02,750 --> 00:18:03,080 All right. 320 00:18:03,080 --> 00:18:04,790 Now let's go ahead and test this function. 321 00:18:04,790 --> 00:18:06,740 So let's call the radix sort function. 322 00:18:06,740 --> 00:18:08,840 And let's have some sample input. 323 00:18:08,840 --> 00:18:11,060 Let's pass in an array over here. 324 00:18:11,720 --> 00:18:14,690 So let's say we are passing the values 380. 325 00:18:15,950 --> 00:18:28,970 Or then we have, let's say 73, 374, then 183 and 65 and 247 and 185. 326 00:18:28,970 --> 00:18:32,360 So let's go ahead and run the code and see what we're getting. 327 00:18:33,620 --> 00:18:34,010 All right. 328 00:18:34,010 --> 00:18:35,330 So let's take a look. 329 00:18:35,870 --> 00:18:36,050 Right. 330 00:18:36,050 --> 00:18:36,980 So we have an error. 331 00:18:36,980 --> 00:18:38,540 Let's take a look at that. 332 00:18:38,540 --> 00:18:40,370 So okay so this should be place. 333 00:18:40,370 --> 00:18:41,930 It's not I it's place. 334 00:18:45,390 --> 00:18:52,620 So over here we have an error because we are saying temp at I is equal to temp at I plus temp I minus 335 00:18:52,620 --> 00:18:53,010 one. 336 00:18:53,010 --> 00:18:54,870 So we cannot start at index zero. 337 00:18:54,870 --> 00:18:57,270 It has to be index one right. 338 00:18:57,270 --> 00:18:59,550 So let's now go ahead and try again. 339 00:18:59,550 --> 00:19:01,440 Now yes you can see it's working. 340 00:19:01,440 --> 00:19:03,510 So this was the array which was given to us. 341 00:19:03,510 --> 00:19:04,770 And you can see it's sorted. 342 00:19:04,770 --> 00:19:10,590 We have 6573 183 185 247 374 and 384. 343 00:19:10,590 --> 00:19:12,150 Now let's take this input. 344 00:19:12,150 --> 00:19:16,770 So this array over here and let's just walk through the code and see what's happening over here to understand 345 00:19:16,770 --> 00:19:18,240 the code in a better manner. 346 00:19:18,840 --> 00:19:23,100 Now let me just write this array over here and then we will just walk through it. 347 00:19:23,100 --> 00:19:24,690 So we have 384. 348 00:19:25,430 --> 00:19:27,230 And then we have 73. 349 00:19:28,350 --> 00:19:30,660 And then we have 374. 350 00:19:31,960 --> 00:19:33,610 And 183. 351 00:19:34,620 --> 00:19:35,760 65. 352 00:19:37,110 --> 00:19:38,400 247. 353 00:19:39,130 --> 00:19:40,630 And 185. 354 00:19:41,220 --> 00:19:42,930 Now let's see what's happening over here. 355 00:19:42,930 --> 00:19:44,850 We are calling the radix sort function. 356 00:19:44,850 --> 00:19:48,510 Now we come inside over here and we see that the array is not empty. 357 00:19:48,510 --> 00:19:50,550 Then we find the greatest number. 358 00:19:50,550 --> 00:19:53,280 So this over here we will find the greatest number. 359 00:19:53,280 --> 00:19:56,190 So among all of these the greatest number is 384. 360 00:19:56,460 --> 00:19:58,710 And then over here we will find the number of digits. 361 00:19:58,710 --> 00:20:01,170 So we are going to take log ten of this. 362 00:20:01,170 --> 00:20:01,500 Right. 363 00:20:01,500 --> 00:20:04,500 So we have seen that log 100 is two. 364 00:20:04,500 --> 00:20:06,990 And for log 1000 we will get three. 365 00:20:06,990 --> 00:20:11,460 So when we do log 384 to the base ten we will get two point something. 366 00:20:11,460 --> 00:20:14,040 And when we floor this we will get two. 367 00:20:14,040 --> 00:20:15,330 And then we are just adding one. 368 00:20:15,330 --> 00:20:18,300 So this is going to give us the number of digits as three. 369 00:20:18,300 --> 00:20:18,720 All right. 370 00:20:18,720 --> 00:20:22,020 So we have found that the number of digits is equal to three. 371 00:20:22,020 --> 00:20:25,410 So we have to call the counting sort function three times. 372 00:20:25,410 --> 00:20:26,880 Now let's go ahead. 373 00:20:26,880 --> 00:20:31,530 So I is going to be zero then one and then two because number of digits is three. 374 00:20:31,530 --> 00:20:35,130 So first we call the counting sort function the helper function. 375 00:20:35,130 --> 00:20:36,660 And we pass in this array. 376 00:20:36,660 --> 00:20:38,700 And I is going to be equal to zero. 377 00:20:39,120 --> 00:20:40,470 Now let's walk through this. 378 00:20:40,470 --> 00:20:41,670 So let's do it for zero. 379 00:20:41,670 --> 00:20:44,790 And then it will do the same thing for the other places as well. 380 00:20:44,790 --> 00:20:47,970 So initially place is zero and the array is passed over here. 381 00:20:47,970 --> 00:20:50,820 Now let's see what's happening in the counting sort function. 382 00:20:50,820 --> 00:20:52,440 So let's just clear this up. 383 00:20:55,700 --> 00:20:56,360 All right. 384 00:20:57,040 --> 00:20:59,950 Now we are inside the counting sort function. 385 00:21:00,760 --> 00:21:04,030 Now, what we're doing is we are going to have this output array. 386 00:21:04,060 --> 00:21:06,070 So this is going to be of the same length. 387 00:21:06,070 --> 00:21:08,440 And we are filling every position with zero. 388 00:21:08,440 --> 00:21:10,870 So our output array is going to look like this. 389 00:21:12,980 --> 00:21:13,250 All right. 390 00:21:13,250 --> 00:21:14,660 So this is the output array. 391 00:21:16,180 --> 00:21:19,780 And then we are going to have a temp array which is of length ten. 392 00:21:21,440 --> 00:21:22,700 So let's just have this over here. 393 00:21:22,700 --> 00:21:24,080 So this is our temp array. 394 00:21:30,320 --> 00:21:37,130 So 012, three four, five, six, seven, eight and nine. 395 00:21:37,130 --> 00:21:42,500 So because we are having numbers in the decimal system, so every digit can only be from 0 to 9. 396 00:21:42,500 --> 00:21:45,230 So that's why the temp array is of length ten. 397 00:21:45,230 --> 00:21:47,270 And then we are filling everything with zero. 398 00:21:49,060 --> 00:21:51,190 So we are having zero everywhere over here. 399 00:21:53,510 --> 00:21:57,110 Then we come over here and we are going to find digit place. 400 00:21:57,110 --> 00:22:00,440 So again we have seen that this is to find the respective digit. 401 00:22:00,440 --> 00:22:00,590 Right. 402 00:22:00,590 --> 00:22:02,570 So let's just walk through and see what's happening. 403 00:22:02,570 --> 00:22:04,700 So at this point place is zero right. 404 00:22:04,700 --> 00:22:06,980 So when we call the function place was zero. 405 00:22:06,980 --> 00:22:09,470 So we are going to take ten to the power zero. 406 00:22:09,470 --> 00:22:11,840 So ten to the power zero is going to be equal to one. 407 00:22:11,840 --> 00:22:13,670 So digit place is one over here. 408 00:22:13,670 --> 00:22:16,670 Now we are looping through the array which is given to us. 409 00:22:16,670 --> 00:22:19,670 So initially we are taking num as 384. 410 00:22:20,180 --> 00:22:23,030 And we are finding digit which is math.floor. 411 00:22:23,030 --> 00:22:25,340 And we are dividing num by digit place. 412 00:22:25,340 --> 00:22:28,040 So 384 is going to be divided by one. 413 00:22:28,040 --> 00:22:30,050 So that's 384 itself. 414 00:22:30,050 --> 00:22:31,640 And then we are doing percentage ten. 415 00:22:31,640 --> 00:22:37,430 So that will give us the remainder when 384 is divided by ten which is equal to four. 416 00:22:37,430 --> 00:22:39,440 So digit is going to be equal to four. 417 00:22:39,440 --> 00:22:45,710 Now we are going to increment the value in the temp array at index four which is over here. 418 00:22:45,710 --> 00:22:47,540 So this is going to be equal to one. 419 00:22:47,630 --> 00:22:49,040 Now let's continue. 420 00:22:49,640 --> 00:22:53,450 We take the next value from the array which is 73. 421 00:22:53,600 --> 00:22:55,580 And then we are going to find the digit. 422 00:22:55,580 --> 00:22:58,070 So 73 divided by one is 73 itself. 423 00:22:58,070 --> 00:22:59,480 And then we do percentage ten. 424 00:22:59,480 --> 00:23:02,720 So that gives us three and then temp at three plus plus. 425 00:23:02,720 --> 00:23:03,950 So that's this over here. 426 00:23:03,950 --> 00:23:05,000 So this becomes one. 427 00:23:05,000 --> 00:23:06,830 Now we go to 374. 428 00:23:06,830 --> 00:23:10,580 So again digit will be four and temp at four will be incremented. 429 00:23:10,580 --> 00:23:11,750 So this becomes two. 430 00:23:11,750 --> 00:23:15,620 And then we take the next value 183 digit will be equal to three. 431 00:23:15,620 --> 00:23:17,360 So at three we are going to increment this. 432 00:23:17,360 --> 00:23:18,470 So we get two over here. 433 00:23:18,470 --> 00:23:20,300 And then we take 65. 434 00:23:20,300 --> 00:23:22,280 So the digit is going to be five. 435 00:23:22,280 --> 00:23:23,510 And then we increment this. 436 00:23:23,510 --> 00:23:24,740 So this is going to be one. 437 00:23:24,740 --> 00:23:27,680 Then 247 digit is going to be seven. 438 00:23:27,680 --> 00:23:29,510 So we increment this to one. 439 00:23:29,510 --> 00:23:32,180 And then we have 185 digit is going to be five. 440 00:23:32,180 --> 00:23:33,830 So this is going to change to two. 441 00:23:33,860 --> 00:23:37,400 So this is how our temp array looks like after this for loop. 442 00:23:37,400 --> 00:23:40,520 Now we come over here and we are going to find the cumulative sum. 443 00:23:40,520 --> 00:23:42,680 So again we have the same temp array. 444 00:23:42,680 --> 00:23:46,940 What we are doing is temp at I is temp at I plus temp at I minus one. 445 00:23:46,940 --> 00:23:49,190 And we are starting with I is equal to one. 446 00:23:49,190 --> 00:23:54,080 So temp at one is going to be tempered one plus temp zero which is zero itself. 447 00:23:54,080 --> 00:23:58,580 Now temp two is going to be tempered two plus tempered one which is zero itself. 448 00:23:58,580 --> 00:24:02,840 Now temp at three is going to be tempered three plus temp at two which is two itself. 449 00:24:02,840 --> 00:24:08,660 Now temp at four is going to be tempered four plus tempered three which is two plus two. 450 00:24:08,690 --> 00:24:10,970 So this value over here changes to four. 451 00:24:12,030 --> 00:24:14,880 And temp at five is going to be two plus four. 452 00:24:14,880 --> 00:24:18,810 So this becomes six, and at six it's going to be six plus zero. 453 00:24:18,810 --> 00:24:20,880 This zero over here which is six itself. 454 00:24:20,880 --> 00:24:23,730 Now temp at seven is going to be this one plus six. 455 00:24:23,730 --> 00:24:25,470 So this becomes seven. 456 00:24:25,470 --> 00:24:27,210 And then over here also we have seven. 457 00:24:27,210 --> 00:24:30,090 And over here also we have seven because these are just zero. 458 00:24:30,090 --> 00:24:33,060 So this is how our temp array looks after this for loop. 459 00:24:33,060 --> 00:24:36,060 Now after this we come over here we come to this for loop. 460 00:24:36,060 --> 00:24:40,290 So we are starting with j equal to r I dot length minus one. 461 00:24:40,290 --> 00:24:43,170 So the length over here is 34567. 462 00:24:43,170 --> 00:24:45,930 So seven minus one J is going to start with six. 463 00:24:45,930 --> 00:24:48,510 So that's index six over here right this one. 464 00:24:48,510 --> 00:24:51,690 So we take this value over here 185. 465 00:24:51,690 --> 00:24:56,160 And then we find the current digit which is 185 divided by one. 466 00:24:56,160 --> 00:25:00,780 So this is 185 divided by one because digit place at this point is one right. 467 00:25:00,780 --> 00:25:02,700 So in the next iteration it will be ten. 468 00:25:02,700 --> 00:25:04,170 So over here it's one. 469 00:25:04,170 --> 00:25:07,020 So 185 by one gives 185 itself. 470 00:25:07,020 --> 00:25:08,460 And then we do percentage ten. 471 00:25:08,460 --> 00:25:10,080 So that that gives us five. 472 00:25:10,080 --> 00:25:12,510 So current digit is going to be equal to five. 473 00:25:13,190 --> 00:25:16,130 And then temp at five we do minus minus. 474 00:25:16,130 --> 00:25:17,000 So let's do that. 475 00:25:17,000 --> 00:25:19,160 So temp at five we have six. 476 00:25:19,160 --> 00:25:21,200 So we're going to decrement this to five. 477 00:25:21,200 --> 00:25:26,090 And then the insert position is going to be temp at current digit which is five right. 478 00:25:26,090 --> 00:25:28,220 So at five in the output array. 479 00:25:28,220 --> 00:25:33,950 So this is our output array at index five we are going to insert array at j which is 185. 480 00:25:33,950 --> 00:25:36,500 So 012345. 481 00:25:36,500 --> 00:25:38,090 So this is five index five. 482 00:25:38,090 --> 00:25:40,310 Over here we are going to have 185. 483 00:25:41,130 --> 00:25:44,760 And then we again proceed to the next number, which is 247. 484 00:25:44,760 --> 00:25:47,370 So let's go ahead and complete this iteration. 485 00:25:47,370 --> 00:25:49,800 So 247 we find current digit. 486 00:25:49,800 --> 00:25:51,570 So current digit is going to be seven. 487 00:25:51,570 --> 00:25:55,980 And we come to the temp array at index seven we have the value seven. 488 00:25:55,980 --> 00:25:57,810 So we decrement this to six. 489 00:25:57,810 --> 00:26:02,010 Now at index six in the output array we are going to insert 247. 490 00:26:02,010 --> 00:26:04,680 So 0123456. 491 00:26:04,680 --> 00:26:05,730 So that's over here. 492 00:26:05,730 --> 00:26:08,850 And we are going to insert 247 over here. 493 00:26:09,360 --> 00:26:10,680 And then we again continue. 494 00:26:10,680 --> 00:26:14,250 We come to 65 and digit is going to be five. 495 00:26:14,250 --> 00:26:17,250 So we come over here at index five we have the value five. 496 00:26:17,250 --> 00:26:18,930 We decrement this to four. 497 00:26:18,930 --> 00:26:22,830 And then at index four in the output array we will insert 65. 498 00:26:22,830 --> 00:26:24,720 So 01234. 499 00:26:24,750 --> 00:26:25,680 That's over here. 500 00:26:25,680 --> 00:26:28,170 So we are going to insert 65 over here. 501 00:26:28,170 --> 00:26:30,000 And then we come to 183. 502 00:26:30,000 --> 00:26:31,740 Current digit is going to be three. 503 00:26:31,740 --> 00:26:34,110 So we come over here at index three we have two. 504 00:26:34,140 --> 00:26:36,000 So this is going to be decremented to one. 505 00:26:36,000 --> 00:26:39,960 So at index one we will insert the next value which is 183. 506 00:26:39,960 --> 00:26:40,770 So zero one. 507 00:26:40,770 --> 00:26:43,260 So over here we will insert 183. 508 00:26:44,400 --> 00:26:45,210 Again, we continue. 509 00:26:45,210 --> 00:26:46,710 We come to 374. 510 00:26:46,740 --> 00:26:48,780 The digit is going to be four, right? 511 00:26:48,780 --> 00:26:50,310 The current digit is going to be four. 512 00:26:50,310 --> 00:26:53,130 And then at index four we have the value four. 513 00:26:53,160 --> 00:26:54,360 This is going to be decremented. 514 00:26:54,360 --> 00:26:55,560 So we get three over here. 515 00:26:55,560 --> 00:27:00,600 Now at index three in the output array we will insert the value which is 374. 516 00:27:00,600 --> 00:27:02,190 So 0123. 517 00:27:02,190 --> 00:27:04,740 So over here we are going to insert 374. 518 00:27:06,990 --> 00:27:07,950 Again we continue. 519 00:27:07,950 --> 00:27:09,300 We come to 73. 520 00:27:09,300 --> 00:27:11,130 Current digit is going to be equal to three. 521 00:27:11,130 --> 00:27:12,240 At three we have one. 522 00:27:12,240 --> 00:27:13,380 So we decrement this. 523 00:27:13,380 --> 00:27:14,490 So we get zero over here. 524 00:27:14,490 --> 00:27:18,150 And at index zero in the output array we will insert 73. 525 00:27:18,150 --> 00:27:19,620 So 73 comes over here. 526 00:27:21,290 --> 00:27:23,300 And then we come to 384. 527 00:27:23,300 --> 00:27:23,630 Right. 528 00:27:23,630 --> 00:27:26,390 So 384 the unit digit is four. 529 00:27:26,390 --> 00:27:27,980 So current digit is going to be four. 530 00:27:27,980 --> 00:27:30,080 So we come to four we decrement this. 531 00:27:30,080 --> 00:27:30,890 So we get two. 532 00:27:30,890 --> 00:27:34,850 So at index 2012 we will insert 384. 533 00:27:36,420 --> 00:27:37,230 So that's it. 534 00:27:37,230 --> 00:27:38,760 So once this is done. 535 00:27:38,910 --> 00:27:43,380 Uh, that's that's how the output array would look at the end of this for loop. 536 00:27:43,380 --> 00:27:49,740 Then we come over here and over here we are just going to loop through this array and change the array 537 00:27:49,740 --> 00:27:50,100 over here. 538 00:27:50,100 --> 00:27:53,820 This array over here is going to be changed to this array which we have just built. 539 00:27:53,820 --> 00:27:55,860 So after this is over. 540 00:27:55,860 --> 00:28:00,480 After this is over, this array over here which we started with is going to look like this. 541 00:28:00,480 --> 00:28:03,360 We'll have 73 then 183. 542 00:28:04,740 --> 00:28:06,570 And then 384. 543 00:28:07,370 --> 00:28:08,630 374. 544 00:28:09,560 --> 00:28:10,610 65. 545 00:28:11,850 --> 00:28:14,490 185 and 247. 546 00:28:15,030 --> 00:28:18,720 So this is after performing counting sort on the unit digits. 547 00:28:18,780 --> 00:28:19,650 Unit digits. 548 00:28:19,650 --> 00:28:20,790 So you can see they are sorted. 549 00:28:20,790 --> 00:28:22,050 So you have three three. 550 00:28:22,080 --> 00:28:23,130 Then you have. 551 00:28:24,410 --> 00:28:25,100 For. 552 00:28:25,100 --> 00:28:30,080 And you have four over here, five over here, five over here and seven over here in in a similar manner. 553 00:28:30,080 --> 00:28:33,050 Again after after this is over, let's just come back. 554 00:28:33,050 --> 00:28:36,560 So after this is over we are again going to call counting sort. 555 00:28:36,560 --> 00:28:38,630 And I is going to be equal to one. 556 00:28:38,630 --> 00:28:38,840 Right. 557 00:28:38,840 --> 00:28:40,880 So I is going to be equal to one at that time. 558 00:28:40,880 --> 00:28:44,930 And then again we'll come inside and we will do the sort for the tens digits. 559 00:28:44,930 --> 00:28:47,150 And after that I is going to be equal to two. 560 00:28:47,150 --> 00:28:49,700 And we will do the sort for the hundredths digits. 561 00:28:49,700 --> 00:28:52,040 And this is how radix sort functions. 562 00:28:52,040 --> 00:28:52,490 All right. 563 00:28:52,490 --> 00:28:54,710 So we have got a good understanding of this. 564 00:28:54,710 --> 00:28:58,670 Now let's take a quick look at the time and space complexity of this solution. 565 00:28:58,670 --> 00:29:04,970 Now the time complexity of this solution is of the order of d into n plus k. 566 00:29:07,920 --> 00:29:11,100 And the space complexity is of the order of n plus k. 567 00:29:12,380 --> 00:29:12,650 All right. 568 00:29:12,650 --> 00:29:14,600 So over here K is the range. 569 00:29:14,600 --> 00:29:16,580 So that's 029 right. 570 00:29:16,580 --> 00:29:17,390 So 0 to 9. 571 00:29:17,390 --> 00:29:20,720 Because this is in decimal system we can say this is just ten. 572 00:29:20,720 --> 00:29:21,980 So let me just change this. 573 00:29:21,980 --> 00:29:26,120 So because this is in decimal system we can say over here we can have ten. 574 00:29:26,120 --> 00:29:28,040 And over here also we can have ten. 575 00:29:31,980 --> 00:29:36,000 And over here D is going to be the maximum number of digits. 576 00:29:36,000 --> 00:29:36,480 All right. 577 00:29:36,480 --> 00:29:41,910 And n is the number of items or number of integers in the array which is given to us. 578 00:29:41,910 --> 00:29:48,450 Now let's try to understand the counting sort will do n plus ten or the operations of the order of n 579 00:29:48,450 --> 00:29:51,300 plus ten or n plus k every time it is called. 580 00:29:51,300 --> 00:29:56,190 And we will call this d number of times, which is done over here in this call, right in this for loop. 581 00:29:56,190 --> 00:30:01,950 That's why the time complexity is going to be of the order of d into n plus k, or because this is the 582 00:30:01,950 --> 00:30:03,960 decimal system D into n plus ten. 583 00:30:03,960 --> 00:30:09,990 And the space complexity is of the order of n plus ten, because every time the counting sort is called, 584 00:30:09,990 --> 00:30:13,410 we will use up space of the order of n plus k or n plus ten. 585 00:30:13,410 --> 00:30:17,460 And again it's it's not going to be d into this because we don't need it. 586 00:30:17,460 --> 00:30:21,240 After one call is over we can just use we can just leave that space or give it up. 587 00:30:21,240 --> 00:30:26,520 So that's why the space complexity of the radix sort and the counting sort is the same, which is of 588 00:30:26,520 --> 00:30:28,410 the order of n plus ten itself. 589 00:30:28,410 --> 00:30:30,360 Now what are the things that take up space? 590 00:30:30,360 --> 00:30:31,890 Let's take a quick look over here. 591 00:30:31,890 --> 00:30:33,660 You can see we have the output array. 592 00:30:34,290 --> 00:30:36,900 So this takes up space of the order of n. 593 00:30:36,900 --> 00:30:40,410 We have this temp array which takes up space of the order of k. 594 00:30:40,410 --> 00:30:42,840 And in this case k is equal to ten. 595 00:30:42,840 --> 00:30:45,150 And we have um is there anything else. 596 00:30:45,150 --> 00:30:45,690 Let's just see. 597 00:30:45,690 --> 00:30:47,640 Is there anything else that takes up space. 598 00:30:47,910 --> 00:30:49,230 No there is nothing else. 599 00:30:49,230 --> 00:30:51,060 So these are the things that take up space. 600 00:30:51,060 --> 00:30:55,290 So we can say that the space complexity is of the order of n plus k. 601 00:30:55,290 --> 00:31:00,570 And because k is equal to ten, we can say it's of the order of n plus ten or which is just o of n. 602 00:31:00,570 --> 00:31:00,990 All right. 603 00:31:01,020 --> 00:31:06,540 Now over here also we can say time complexity is of the order of D into n, because over here k is a 604 00:31:06,540 --> 00:31:07,590 constant which is ten. 605 00:31:07,590 --> 00:31:11,190 Now let's also take a look at the things that take up uh time. 606 00:31:11,190 --> 00:31:13,080 So again we have seen that over here. 607 00:31:13,080 --> 00:31:14,220 We are doing it d times. 608 00:31:14,220 --> 00:31:15,420 So we have a D over here. 609 00:31:15,420 --> 00:31:19,110 And the counting sort is of the order of n plus k. 610 00:31:19,110 --> 00:31:24,180 So let's see what are the things that take up space or take up time in the uh counting sort. 611 00:31:24,180 --> 00:31:25,620 So let's take a look at that. 612 00:31:26,160 --> 00:31:28,530 So we have the counting sort function over here. 613 00:31:29,870 --> 00:31:31,010 Now we are. 614 00:31:31,010 --> 00:31:34,880 We are going to take up time when we determine the frequencies, right? 615 00:31:34,880 --> 00:31:36,080 For example, over here. 616 00:31:37,290 --> 00:31:39,570 This is going to take up N operations. 617 00:31:39,570 --> 00:31:39,930 Right. 618 00:31:39,930 --> 00:31:42,750 So we are looping through the array and there are n elements over here. 619 00:31:42,750 --> 00:31:44,400 So this is going to be n operation here. 620 00:31:44,400 --> 00:31:46,890 Also we are going to have n operations right. 621 00:31:46,890 --> 00:31:49,980 Because we have to loop through the output array and fill it with zero. 622 00:31:49,980 --> 00:31:54,690 And over here also we are going to have k operations because that's going to be the length of the temp 623 00:31:54,690 --> 00:31:54,870 array. 624 00:31:54,870 --> 00:31:55,170 Right. 625 00:31:55,170 --> 00:31:58,140 And then we are looping through the temporary and filling with zero. 626 00:31:58,140 --> 00:32:00,630 And again we have seen over here we have N operations. 627 00:32:00,630 --> 00:32:05,580 And then over here you can see we are looping through the temp array. 628 00:32:05,580 --> 00:32:07,770 And we are finding the cumulative sum. 629 00:32:07,770 --> 00:32:10,440 So this is going to be again k operations. 630 00:32:10,440 --> 00:32:10,950 Right. 631 00:32:10,950 --> 00:32:17,310 And over here we are looping again through the array right to fill the output um array with the correct 632 00:32:17,310 --> 00:32:17,700 elements. 633 00:32:17,700 --> 00:32:20,340 So this is again going to be another n operations. 634 00:32:20,340 --> 00:32:23,610 And inside this the operations are just constant time operations. 635 00:32:23,610 --> 00:32:28,020 That's why you can see there are total of n three times n and two times k. 636 00:32:28,020 --> 00:32:30,000 So we could say three n plus two k. 637 00:32:30,000 --> 00:32:33,210 But that's just n plus k because we are avoiding the constants. 638 00:32:33,210 --> 00:32:37,080 So that's why the time complexity of the counting sort is n plus k. 639 00:32:37,080 --> 00:32:38,760 And we are calling it d times. 640 00:32:38,760 --> 00:32:45,510 So hence we can say the time complexity of this solution is of the order of d into n plus k or d into 641 00:32:45,510 --> 00:32:46,230 n plus ten. 642 00:32:46,230 --> 00:32:48,750 Because over here we are dealing with decimal system. 643 00:32:48,750 --> 00:32:51,960 And we could say we can simplify this further. 644 00:32:51,960 --> 00:32:58,410 We could say the time complexity is of the order of d into n, because this is also a constant in this 645 00:32:58,410 --> 00:32:58,680 case. 646 00:32:58,680 --> 00:33:01,440 And the space complexity is of the order of n.