1
00:00:00,680 --> 00:00:02,960
Hi everyone, let's do this question.

2
00:00:02,960 --> 00:00:05,900
You are given an array of non-negative integers.

3
00:00:05,900 --> 00:00:12,380
Write a function that will take this array as input and return the sorted array using radix sort.

4
00:00:12,380 --> 00:00:17,270
So over here we are going to learn how to implement radix sort, and also take a note that it's given

5
00:00:17,270 --> 00:00:20,330
in the question that the integers are non-negative.

6
00:00:20,330 --> 00:00:25,460
Now, if it is mentioned that the integers can be negative, then the way you implement the radix sort

7
00:00:25,460 --> 00:00:26,540
will be a little bit different.

8
00:00:26,540 --> 00:00:31,580
But over here in this question we are dealing with radix sort where the integers are non-negative.

9
00:00:31,580 --> 00:00:35,180
Now in this section we are going to have three parts.

10
00:00:35,180 --> 00:00:39,590
First, we will try to develop an intuition on how the radix sort works.

11
00:00:39,590 --> 00:00:43,160
After this, we will go ahead and learn the counting sort algorithm.

12
00:00:43,160 --> 00:00:48,890
And we are learning this algorithm over here because we will be using the counting sort algorithm in

13
00:00:48,890 --> 00:00:51,440
part three to implement the radix sort.

14
00:00:51,440 --> 00:00:53,000
So this is how we will proceed.

15
00:00:53,000 --> 00:00:58,310
Now let's go ahead and develop an intuition on how the radix sort works.

16
00:00:58,310 --> 00:01:00,530
Now for this, let's take an example.

17
00:01:00,530 --> 00:01:03,560
Let's say the array which is given to us is this one over here.

18
00:01:03,560 --> 00:01:08,090
That is 123, 78, 63, 19 and five.

19
00:01:08,660 --> 00:01:15,920
Now how the radix sort works is that first we will sort these numbers only based on the digit in their

20
00:01:15,920 --> 00:01:16,790
units place.

21
00:01:16,790 --> 00:01:21,260
So for example, in 123 the digit in the units place is three.

22
00:01:21,260 --> 00:01:27,110
Similarly, in 78 it is eight, in 63 it is three, and in 19 we have nine.

23
00:01:27,110 --> 00:01:28,400
And over here we have five.

24
00:01:28,400 --> 00:01:30,470
So let's go ahead and see how this works.

25
00:01:30,470 --> 00:01:34,430
So let's sort these numbers based on the digit in their units place.

26
00:01:34,430 --> 00:01:36,830
So we can see that the lowest value is three.

27
00:01:36,830 --> 00:01:38,900
So we have 123 itself over here.

28
00:01:38,900 --> 00:01:41,060
And after this we have 63.

29
00:01:41,060 --> 00:01:42,890
And you can see that there is a tie over here.

30
00:01:42,890 --> 00:01:43,040
Right.

31
00:01:43,040 --> 00:01:44,750
You have three over here and over here.

32
00:01:44,750 --> 00:01:48,470
So in that case the initial relative ordering is maintained.

33
00:01:48,470 --> 00:01:50,930
So we have 123 then 63.

34
00:01:50,930 --> 00:01:55,970
After this we will get five because after three the next greatest value in the units digit over here

35
00:01:55,970 --> 00:01:56,570
is five.

36
00:01:56,570 --> 00:01:57,920
So we have five over here.

37
00:01:57,920 --> 00:02:00,260
And after five we have 78.

38
00:02:00,260 --> 00:02:01,760
Then we have 19.

39
00:02:01,760 --> 00:02:07,130
So we just sorted these numbers which were given to us based on the digit in the units place.

40
00:02:07,130 --> 00:02:13,160
Now what we will do is we will go ahead and sort these numbers based on the digit in the tens place,

41
00:02:13,160 --> 00:02:17,060
which is two, six, zero, seven and one.

42
00:02:17,060 --> 00:02:18,710
And over here there was nothing.

43
00:02:18,710 --> 00:02:23,120
So that's why we have written zero, because we can write five as zero five also.

44
00:02:23,120 --> 00:02:24,830
Now let's go ahead and sort them.

45
00:02:24,830 --> 00:02:26,630
So the least value is zero.

46
00:02:26,630 --> 00:02:28,340
So zero five comes first.

47
00:02:28,340 --> 00:02:33,230
Then we have 19, then one 2363 and then 78.

48
00:02:33,230 --> 00:02:36,320
Now you can see that the numbers are sorted as per their 10th digit.

49
00:02:36,320 --> 00:02:39,200
So zero, one, two, six and seven.

50
00:02:39,200 --> 00:02:44,990
Now what we will do is we will go ahead and sort these numbers based on the digit in their hundredths

51
00:02:44,990 --> 00:02:46,610
place hundredths place over here.

52
00:02:46,610 --> 00:02:53,120
And if there is nothing then we will just mark zero over there because again we can write five as 005

53
00:02:53,120 --> 00:02:53,660
also.

54
00:02:53,660 --> 00:02:54,890
So let's go ahead and do that.

55
00:02:54,890 --> 00:02:56,300
So we have zero zero.

56
00:02:56,300 --> 00:02:58,430
And then we have one over here and over here.

57
00:02:58,430 --> 00:02:59,780
And here also we have zero.

58
00:02:59,780 --> 00:03:02,690
So there is a tie between these four numbers.

59
00:03:02,690 --> 00:03:04,820
So the initial order is maintained.

60
00:03:04,820 --> 00:03:07,100
And then we have 123 coming last.

61
00:03:07,100 --> 00:03:15,710
So when we order these numbers based on their hundredths digit we get 519 6378 and 123.

62
00:03:15,710 --> 00:03:17,510
So this is how radix sort works.

63
00:03:17,510 --> 00:03:20,600
And you can see that these numbers over here are now sorted.

64
00:03:20,600 --> 00:03:21,890
So this was the initial array.

65
00:03:21,890 --> 00:03:24,350
And you can see that the numbers over here are sorted.

66
00:03:24,350 --> 00:03:25,700
Now what did we do.

67
00:03:25,730 --> 00:03:32,540
We sorted the numbers initially based on the digit at the ones place, then at the tenths place and

68
00:03:32,540 --> 00:03:34,190
then at the hundredths place.

69
00:03:34,190 --> 00:03:39,080
Now we did not proceed to the thousandths place because there is no number in the array which is given

70
00:03:39,080 --> 00:03:43,340
to us, which has any digit in the thousandths place, so we can stop at.

71
00:03:43,340 --> 00:03:48,710
So the number of times we have to keep doing is till the largest place in any of the numbers, which

72
00:03:48,710 --> 00:03:49,700
is given in the array.

73
00:03:49,700 --> 00:03:52,490
And you can see that that's the hundredths place over here.

74
00:03:52,490 --> 00:03:55,580
So that's why we had to keep doing it till the hundredths place.

75
00:03:55,580 --> 00:03:57,140
Now why does this work.

76
00:03:57,440 --> 00:04:03,170
We can see that initially when we sorted the numbers based on their ones place, we got this over here.

77
00:04:03,170 --> 00:04:03,560
All right.

78
00:04:03,590 --> 00:04:09,350
Now after this, when we sorted the numbers based on their tenths place, you can see that whatever

79
00:04:09,350 --> 00:04:12,740
was wrong over here with respect to the tenths place gets rectified over here.

80
00:04:12,740 --> 00:04:13,010
Right.

81
00:04:13,010 --> 00:04:16,910
For example, you can see 123 is ahead of zero five.

82
00:04:16,910 --> 00:04:21,140
But that is changed because now you have zero over here and then you have two over here.

83
00:04:21,140 --> 00:04:21,470
Right.

84
00:04:21,470 --> 00:04:23,450
And then again you have 63 over here.

85
00:04:23,450 --> 00:04:24,440
And then you have five.

86
00:04:24,440 --> 00:04:26,030
So this is also rectified over here.

87
00:04:26,030 --> 00:04:26,180
Right.

88
00:04:26,180 --> 00:04:28,340
Because you have six over here and zero over here.

89
00:04:28,340 --> 00:04:33,830
And then finally whatever is wrong over here is rectified by sorting based on the hundredths place.

90
00:04:33,830 --> 00:04:36,170
So 123 came last.

91
00:04:36,170 --> 00:04:37,880
So we shifted its position to the last.

92
00:04:37,880 --> 00:04:42,620
And then this works because if there is a tie the initial ordering is maintained.

93
00:04:42,620 --> 00:04:44,180
So that's the important thing over here.

94
00:04:44,180 --> 00:04:47,390
Now for example notice that we have five and 19 over here.

95
00:04:47,390 --> 00:04:50,750
And we have zero in both the cases in their hundredths place.

96
00:04:50,750 --> 00:04:55,340
And when we sorted based on the hundredths place, we did not change their relative positioning.

97
00:04:55,340 --> 00:04:56,540
So we maintained it.

98
00:04:56,540 --> 00:04:58,220
So you can see that we maintained it.

99
00:04:58,220 --> 00:04:59,660
So if nothing is there any way it's.

100
00:04:59,760 --> 00:05:02,700
Going to be just zero over here and we are maintaining the previous order.

101
00:05:02,700 --> 00:05:04,320
So that's why this is working.

102
00:05:04,320 --> 00:05:10,500
And you can note that maintaining the previous relative positions in case of a tie is a very important

103
00:05:10,500 --> 00:05:13,050
thing to have the radix sort work.

104
00:05:13,050 --> 00:05:15,150
And that's why we will see later.

105
00:05:15,150 --> 00:05:21,360
That's that's the reason that's one of the reasons why we are why we will use counting sort to implement

106
00:05:21,360 --> 00:05:22,050
radix sort.

107
00:05:22,050 --> 00:05:22,470
Again.

108
00:05:22,470 --> 00:05:24,810
We will see that in part two and part three.

109
00:05:24,810 --> 00:05:29,160
Now let's proceed now again just to mention over here to get to this.

110
00:05:29,160 --> 00:05:33,510
That is to sort based on one's digits and ten's digits and hundreds digits, digits.

111
00:05:33,510 --> 00:05:35,160
We will use counting sort.

112
00:05:35,160 --> 00:05:38,100
And we will see that in the latter part of this section.

113
00:05:38,100 --> 00:05:43,560
Again, one more reason why this is being done is that this has good time complexity, the counting

114
00:05:43,560 --> 00:05:43,830
sort.

115
00:05:43,830 --> 00:05:45,480
And this is stable.

116
00:05:45,480 --> 00:05:50,670
And with stable, we mean that in the case of a tie, as in what we have seen over here or over here,

117
00:05:50,670 --> 00:05:53,880
the initial relative ordering is maintained.

118
00:05:53,880 --> 00:05:54,360
All right.

119
00:05:54,360 --> 00:05:56,160
So we are done with step one.

120
00:05:56,160 --> 00:05:58,860
We have developed an intuition on how radix sort works.

121
00:05:58,860 --> 00:06:02,670
So it's not actually going to compare the values of two numbers.

122
00:06:02,670 --> 00:06:07,770
Rather what we are doing is we are going to take first only the units digits and then sort the numbers

123
00:06:07,770 --> 00:06:10,800
based on those digits, then the tens, digits, etc..

124
00:06:10,800 --> 00:06:12,690
So this is how radix sort works.

125
00:06:12,690 --> 00:06:16,710
Now let's go ahead and try to understand how counting sort works.

126
00:06:16,710 --> 00:06:20,910
And then in part three we will use counting sort to implement radix sort.

127
00:06:20,910 --> 00:06:22,890
So let's get started with part two.

128
00:06:23,720 --> 00:06:24,110
All right.

129
00:06:24,110 --> 00:06:26,510
Now we are going to learn the counting sort.

130
00:06:27,370 --> 00:06:35,680
Now we know that for any good sorting algorithm, the time complexity is of the order of n log n.

131
00:06:35,710 --> 00:06:40,630
Now this is the fastest we can sort when we know nothing about the input.

132
00:06:40,630 --> 00:06:41,080
All right.

133
00:06:41,110 --> 00:06:47,950
Now again this is this, this time complexity is achieved which is the best possible in the case of

134
00:06:47,950 --> 00:06:49,840
comparison based sorting.

135
00:06:49,870 --> 00:06:54,010
Now to do better than this we have the counting sort.

136
00:06:54,010 --> 00:06:58,090
And the counting sort is not a comparison based sorting.

137
00:06:58,090 --> 00:06:58,450
All right.

138
00:06:58,480 --> 00:07:00,040
Now let's see how we can do this.

139
00:07:00,040 --> 00:07:04,870
And again the reason why we are attempting this is to do better than o of n log n.

140
00:07:05,470 --> 00:07:09,490
And this is possible when we know something about the input.

141
00:07:09,520 --> 00:07:14,230
Now, in the case where we know nothing about the input, we cannot do better than O of n log n.

142
00:07:14,230 --> 00:07:20,110
But in the case where we know or we have some info about the input, let's see how we can make use of

143
00:07:20,110 --> 00:07:22,030
this information to do better.

144
00:07:22,670 --> 00:07:28,070
The reason why we can use counting sort is because we have some information about the input.

145
00:07:28,070 --> 00:07:33,680
And this information which we have is that the numbers will lie between zero and k.

146
00:07:33,680 --> 00:07:34,520
And what is this?

147
00:07:34,550 --> 00:07:35,180
Why is this so?

148
00:07:35,180 --> 00:07:37,400
Because we are taking only the digits, right?

149
00:07:37,400 --> 00:07:42,320
First we are just taking the digits in the units place, then in the tens, place, etc. now digits

150
00:07:42,320 --> 00:07:44,960
can only lie between 0 and 9, right?

151
00:07:44,960 --> 00:07:50,420
So we know that every digit is going to be between 0 and 9 and both of them included.

152
00:07:50,420 --> 00:07:53,420
So this is what we know about the input.

153
00:07:53,420 --> 00:07:57,410
And we will make use of this information to implement the counting sort.

154
00:07:57,410 --> 00:08:00,110
So let's go ahead and see how we can do this.

155
00:08:00,500 --> 00:08:04,160
Now let's say this is the array which is given to us.

156
00:08:04,160 --> 00:08:04,460
All right.

157
00:08:04,460 --> 00:08:05,720
So this is the input array.

158
00:08:05,720 --> 00:08:11,090
And over here let's say each element lies in the range between 0 and 9.

159
00:08:11,090 --> 00:08:13,460
Now again tying this back to the radix sort.

160
00:08:13,460 --> 00:08:18,260
Remember we are only sorting first for based on what is there in the units place.

161
00:08:18,260 --> 00:08:20,000
So that's just one digit, right?

162
00:08:20,000 --> 00:08:23,330
Even though the number may be something like 123 for example.

163
00:08:23,330 --> 00:08:30,470
And let's say 123, 45, 67, etc. when we only take the units digit, this becomes equivalent to three,

164
00:08:30,470 --> 00:08:32,840
this is five and then this is seven.

165
00:08:32,840 --> 00:08:38,840
Now the position of 123 is just determined by what is there in the units digit.

166
00:08:38,840 --> 00:08:41,180
So that's why we can neglect this.

167
00:08:41,180 --> 00:08:43,580
And we are only focusing on the units digit.

168
00:08:43,580 --> 00:08:48,410
So what we have on the units digit, for example, when we are dealing with the part where we sort on

169
00:08:48,410 --> 00:08:49,610
the basis of the units digit.

170
00:08:49,610 --> 00:08:56,330
So in that case we can say that each integer is represented by one digit, and that will lie in the

171
00:08:56,330 --> 00:08:57,800
range of 0 to 9.

172
00:08:57,800 --> 00:08:59,360
Now let's take an example.

173
00:08:59,360 --> 00:09:02,990
Let's say we have 12345678.

174
00:09:02,990 --> 00:09:05,030
Let's say we have eight numbers to sort.

175
00:09:05,030 --> 00:09:08,330
And let's say we are just considering their digit, right.

176
00:09:08,330 --> 00:09:09,200
One digit at a time.

177
00:09:09,200 --> 00:09:13,820
So let's say the digits are seven, five three, zero, one, three, seven and eight.

178
00:09:13,820 --> 00:09:19,820
Now let's try to keep this apart for a moment, and we will come back and see how we can implement or

179
00:09:19,820 --> 00:09:21,380
make use of the counting sort.

180
00:09:21,380 --> 00:09:23,330
In the case of radix sort.

181
00:09:23,330 --> 00:09:28,910
But over here, let's first try to understand how counting sort is able to sort these numbers.

182
00:09:28,910 --> 00:09:33,290
So let's say these are the numbers which are given to us, which is seven, five three, zero, one,

183
00:09:33,290 --> 00:09:34,670
three, seven and eight.

184
00:09:34,670 --> 00:09:36,620
So you can see there are eight numbers.

185
00:09:36,620 --> 00:09:39,560
Now how do we use counting sort to sort them.

186
00:09:39,560 --> 00:09:43,280
So for this first we will have an auxiliary array.

187
00:09:44,030 --> 00:09:44,450
All right.

188
00:09:44,450 --> 00:09:47,720
And these will have the indices from 0 to 9.

189
00:09:47,720 --> 00:09:52,850
Because we know that the elements or the digits which are there over here can only be in the range of

190
00:09:52,850 --> 00:09:53,630
0 to 9.

191
00:09:53,630 --> 00:09:56,090
So that's why we have the indices 0 to 9 over here.

192
00:09:56,090 --> 00:10:02,450
Now what we will do is we will just loop through the array which is given to us, which is 75301378.

193
00:10:02,450 --> 00:10:08,240
And then whenever we encounter a particular number, we will increment the value in that particular

194
00:10:08,240 --> 00:10:08,750
index.

195
00:10:08,750 --> 00:10:11,810
So for example let's say everything is zero at this point.

196
00:10:11,810 --> 00:10:12,290
All right.

197
00:10:12,290 --> 00:10:15,470
And then when we come to seven we will change that to one.

198
00:10:15,470 --> 00:10:18,170
And when we come to five this also will change to one.

199
00:10:18,170 --> 00:10:20,900
And when we see the second seven this will go to two.

200
00:10:20,930 --> 00:10:26,750
So we are basically so we are just taking the number of times these integers are occurring in this array

201
00:10:26,750 --> 00:10:27,710
which is given to us.

202
00:10:27,710 --> 00:10:30,980
So once we go through the array we will see this right.

203
00:10:30,980 --> 00:10:32,390
We can see that zero is occurring.

204
00:10:32,390 --> 00:10:36,410
Once you can see one is occurring one time and then two is occurring.

205
00:10:36,410 --> 00:10:40,850
Zero times three is occurring twice once here and once here four is occurring.

206
00:10:40,850 --> 00:10:43,670
Zero times five is occurring once six is occurring.

207
00:10:43,670 --> 00:10:45,320
Zero times seven is occurring.

208
00:10:45,350 --> 00:10:49,250
Two times eight is eight is occurring once and nine is not occurring.

209
00:10:49,250 --> 00:10:53,960
So this is what we get now after we have this frequency array over here.

210
00:10:53,960 --> 00:10:58,070
What we will do is we will go ahead and take the cumulative sum.

211
00:10:58,070 --> 00:10:58,460
All right.

212
00:10:58,460 --> 00:11:00,110
So what is the cumulative sum.

213
00:11:00,110 --> 00:11:03,230
We are just going to add these up as we go from left to right.

214
00:11:03,230 --> 00:11:07,250
So in position zero we just have what is there which is one itself.

215
00:11:07,250 --> 00:11:13,130
But at index one we will have the sum of what is there at index zero and at index one.

216
00:11:13,130 --> 00:11:15,410
So one plus one gives two over here.

217
00:11:15,410 --> 00:11:19,700
Similarly at index two we will have this zero plus this two.

218
00:11:19,730 --> 00:11:20,150
All right.

219
00:11:20,150 --> 00:11:21,560
So that gives us two again.

220
00:11:21,560 --> 00:11:27,440
Now at index three we will have this two plus this two which is equal to four.

221
00:11:27,830 --> 00:11:31,850
And similarly at index four we will have four plus zero which is four.

222
00:11:31,850 --> 00:11:36,560
At index five we will have this four plus one which is equal to five.

223
00:11:36,560 --> 00:11:40,970
And in the next position also we will have five because over here we have zero.

224
00:11:40,970 --> 00:11:42,050
And over here we have five.

225
00:11:42,050 --> 00:11:43,130
So we are adding these up.

226
00:11:43,130 --> 00:11:44,300
We are getting five over here.

227
00:11:44,300 --> 00:11:45,500
Then five plus two.

228
00:11:45,500 --> 00:11:46,880
That gives us seven over here.

229
00:11:46,880 --> 00:11:50,870
Similarly seven plus one gives us eight and eight plus zero gives us eight.

230
00:11:50,870 --> 00:11:53,060
So this is the cumulative sum that we have.

231
00:11:53,060 --> 00:11:53,540
All right.

232
00:11:53,540 --> 00:11:56,900
Now we need one more array which is the output array.

233
00:11:56,900 --> 00:12:00,830
The output array is going to have an equal number of elements as the input array.

234
00:12:00,830 --> 00:12:03,650
So over here we have seen it has eight elements right.

235
00:12:03,650 --> 00:12:06,290
So the output array is also going to have eight elements.

236
00:12:06,290 --> 00:12:07,910
So this is our output array.

237
00:12:08,420 --> 00:12:11,540
And let's just say the indices are from 0 to 7.

238
00:12:11,540 --> 00:12:11,840
All right.

239
00:12:11,840 --> 00:12:12,950
So this is the output array.

240
00:12:12,980 --> 00:12:16,640
Now what we will do is we will go backwards.

241
00:12:16,640 --> 00:12:20,570
That is we will start at the end of the given array or the input array.

242
00:12:20,570 --> 00:12:21,860
And we will go backwards.

243
00:12:22,230 --> 00:12:23,670
So we will see why.

244
00:12:23,670 --> 00:12:26,280
This is why we do it in this manner again.

245
00:12:26,370 --> 00:12:30,540
This is useful to maintain the stability or the relative ordering.

246
00:12:30,540 --> 00:12:31,620
So we will see that soon.

247
00:12:31,620 --> 00:12:37,140
Why we do that now for for the moment, let's just go with the algorithm and let's try to understand

248
00:12:37,140 --> 00:12:37,860
how it works.

249
00:12:37,860 --> 00:12:39,690
Now first we take eight.

250
00:12:39,690 --> 00:12:40,050
All right.

251
00:12:40,050 --> 00:12:41,460
We take this value eight.

252
00:12:41,460 --> 00:12:46,110
Now we have to decide where should we keep this eight in the output array.

253
00:12:46,110 --> 00:12:46,650
All right.

254
00:12:46,680 --> 00:12:52,020
Now to identify the position where this has to be inserted in the output array, we will take a look

255
00:12:52,020 --> 00:12:54,630
at the cumulative sum array which we have over here.

256
00:12:54,630 --> 00:12:57,060
And we will take this index over here which is eight.

257
00:12:57,060 --> 00:12:59,220
So we will take a look at this eight over here.

258
00:12:59,610 --> 00:13:05,010
Now at this position eight the value is equal to eight which is this eight inside.

259
00:13:05,010 --> 00:13:05,460
All right.

260
00:13:05,460 --> 00:13:06,990
Now what does this mean.

261
00:13:06,990 --> 00:13:13,140
This eight over here means that there are eight elements which are less than or equal to the value eight

262
00:13:13,140 --> 00:13:15,450
in the array which is given to us.

263
00:13:15,450 --> 00:13:15,840
All right.

264
00:13:15,840 --> 00:13:17,070
So that's the meaning of this.

265
00:13:17,070 --> 00:13:22,800
So if there are eight elements which are less than or equal to eight, then we have to insert it in

266
00:13:22,800 --> 00:13:25,740
in a manner such that this is true.

267
00:13:25,740 --> 00:13:26,070
Right.

268
00:13:26,070 --> 00:13:29,250
So what we will do is we will subtract one from this.

269
00:13:29,250 --> 00:13:31,260
So eight minus one gives us seven.

270
00:13:31,260 --> 00:13:34,740
And we will insert this value eight at index seven.

271
00:13:34,740 --> 00:13:36,240
So that's going to be over here.

272
00:13:36,240 --> 00:13:38,160
This is index seven in the output array.

273
00:13:38,160 --> 00:13:41,790
So we will insert this eight at index seven which is over here.

274
00:13:41,790 --> 00:13:47,040
Now when we do this you can see that this eight has eight elements less than eight.

275
00:13:47,040 --> 00:13:47,220
Right.

276
00:13:47,220 --> 00:13:51,960
So this is the eight over here you can see 12345678.

277
00:13:51,960 --> 00:13:55,740
So there are indeed eight elements less than or equal to this eight.

278
00:13:55,740 --> 00:13:58,740
So that's why we have that's why we have inserted it at seven.

279
00:13:58,740 --> 00:14:03,480
And again we have subtracted one over here because you can see this is zero index right.

280
00:14:03,480 --> 00:14:04,770
So it's starting at zero.

281
00:14:04,770 --> 00:14:06,090
That's why we subtract one.

282
00:14:06,090 --> 00:14:11,310
So we get seven and we insert the value eight which is this one over here at index seven.

283
00:14:11,310 --> 00:14:12,240
This seven over here.

284
00:14:12,330 --> 00:14:13,830
And then let's continue.

285
00:14:14,190 --> 00:14:18,570
What we will do is we will go ahead and take the next value which is seven.

286
00:14:18,570 --> 00:14:20,070
So over here we have seven.

287
00:14:20,070 --> 00:14:21,390
All right now.

288
00:14:22,350 --> 00:14:23,970
You can see we have we have seven.

289
00:14:23,970 --> 00:14:24,780
Let me just circle this.

290
00:14:24,780 --> 00:14:25,950
So we have seven over here.

291
00:14:25,950 --> 00:14:29,460
Now what we will do again, we will come to the cumulative sum array.

292
00:14:29,460 --> 00:14:32,910
And we will take a look at what is there at index seven.

293
00:14:32,910 --> 00:14:35,490
Now at index seven we have seven.

294
00:14:35,490 --> 00:14:35,880
All right.

295
00:14:35,880 --> 00:14:41,430
So this means that there are seven elements which are less than or equal to seven in the array.

296
00:14:41,430 --> 00:14:41,790
All right.

297
00:14:41,790 --> 00:14:45,330
So when when it is sorted so what we will do we will take this value.

298
00:14:45,360 --> 00:14:47,010
We will decrement it by one.

299
00:14:47,010 --> 00:14:47,340
Again.

300
00:14:47,340 --> 00:14:47,910
Why is that so.

301
00:14:47,910 --> 00:14:49,050
Because it's zero index.

302
00:14:49,050 --> 00:14:50,430
We get the value six.

303
00:14:50,430 --> 00:14:53,970
And we are going to insert this seven over here at index six.

304
00:14:53,970 --> 00:14:54,210
All right.

305
00:14:54,210 --> 00:14:55,290
So this is index six.

306
00:14:55,290 --> 00:14:56,790
So let's insert it over here.

307
00:14:56,790 --> 00:14:59,850
Now when we insert it we have seven over here.

308
00:15:00,490 --> 00:15:04,810
Now you can see there are seven elements which are less than or equal to this seven.

309
00:15:05,020 --> 00:15:05,410
One.

310
00:15:05,410 --> 00:15:06,070
Two three.

311
00:15:06,070 --> 00:15:06,430
Four.

312
00:15:06,430 --> 00:15:06,790
Five.

313
00:15:06,790 --> 00:15:07,060
Six.

314
00:15:07,060 --> 00:15:07,480
Seven.

315
00:15:07,630 --> 00:15:09,400
That's why we have inserted it over here.

316
00:15:09,400 --> 00:15:10,390
Again we proceed.

317
00:15:10,390 --> 00:15:12,250
We take the next element which is three.

318
00:15:12,430 --> 00:15:19,060
Now for identifying where to insert this three in the output array we will take a look at index three

319
00:15:19,060 --> 00:15:21,550
in the cumulative sum array which is over here right.

320
00:15:21,550 --> 00:15:27,880
So we have three over here at index three the value is four which means that there are four values four

321
00:15:27,880 --> 00:15:32,980
elements which are less than or equal to three in the output array, which is which is the case when

322
00:15:32,980 --> 00:15:34,420
the values are sorted.

323
00:15:34,420 --> 00:15:39,550
So to find where to insert this particular three, we will decrement this four by one.

324
00:15:39,550 --> 00:15:45,070
So we get three over here and we will insert this three at index three which is over here.

325
00:15:45,070 --> 00:15:46,600
So let's go ahead and insert it.

326
00:15:46,600 --> 00:15:47,890
So we have three over here.

327
00:15:47,890 --> 00:15:54,640
And you can see you have 123 and four four elements which are less than or equal to three in the output

328
00:15:54,640 --> 00:15:55,060
array.

329
00:15:55,060 --> 00:15:56,140
Again we proceed.

330
00:15:56,140 --> 00:15:57,550
We take one over here.

331
00:15:58,120 --> 00:15:59,080
So we take one.

332
00:15:59,080 --> 00:16:02,200
Now we have to decide where to insert one in the output array.

333
00:16:02,200 --> 00:16:04,870
So again we will take a look at the cumulative sum array.

334
00:16:04,870 --> 00:16:10,810
At index one the value is equal to two which means that there are two elements less than or equal to

335
00:16:10,810 --> 00:16:12,370
one in the output array.

336
00:16:12,370 --> 00:16:16,450
Now to know where to insert this one, we will take this value and decrement it by one.

337
00:16:16,450 --> 00:16:18,010
So we get one over here.

338
00:16:18,010 --> 00:16:21,670
And we are going to insert this value at index one which is over here.

339
00:16:21,670 --> 00:16:23,560
So let's go ahead and write one over here.

340
00:16:23,560 --> 00:16:25,060
And we have one over here.

341
00:16:25,060 --> 00:16:27,880
And you can see you have two elements less than or equal to one.

342
00:16:27,880 --> 00:16:28,990
This is the element one.

343
00:16:28,990 --> 00:16:29,980
And this is element two.

344
00:16:30,010 --> 00:16:32,560
So two elements less than or equal to one.

345
00:16:32,560 --> 00:16:33,520
Let's proceed.

346
00:16:33,520 --> 00:16:35,500
We go to the next element which is zero.

347
00:16:35,500 --> 00:16:39,040
And now we have to decide where to insert it in our output array.

348
00:16:39,040 --> 00:16:41,710
So again we take a look at the cumulative sum array.

349
00:16:41,710 --> 00:16:43,690
And we take a look at index zero.

350
00:16:43,690 --> 00:16:45,670
And we decrement the value by one.

351
00:16:45,670 --> 00:16:46,600
So we get zero.

352
00:16:46,600 --> 00:16:49,840
And we're going to insert this zero at index zero.

353
00:16:50,440 --> 00:16:55,690
So you can see there is one element which is less than or equal to zero in the output array which is

354
00:16:55,690 --> 00:16:56,860
this element itself.

355
00:16:56,860 --> 00:16:59,080
Again notice it's less than or equal to.

356
00:16:59,110 --> 00:17:00,460
Now let's again proceed.

357
00:17:00,460 --> 00:17:02,710
So we come to the next element which is three.

358
00:17:02,710 --> 00:17:07,000
Now we have to decide where to insert this three this three in the output array.

359
00:17:07,210 --> 00:17:11,440
Now for this we take a look at the cumulative sum array at index three the value is three.

360
00:17:11,440 --> 00:17:13,420
So we are going to decrease this by one.

361
00:17:13,420 --> 00:17:14,530
And we get two.

362
00:17:14,530 --> 00:17:17,950
And we are going to insert this three at index two which is over here.

363
00:17:17,950 --> 00:17:19,630
So let's go ahead and insert it.

364
00:17:19,630 --> 00:17:21,100
So we get three over here.

365
00:17:21,730 --> 00:17:24,250
And you can see you have two.

366
00:17:24,460 --> 00:17:25,480
You have three elements.

367
00:17:25,480 --> 00:17:26,350
This was three right.

368
00:17:26,350 --> 00:17:31,300
You have three elements one two and three which is less than or equal to this three over here.

369
00:17:31,300 --> 00:17:32,830
Now again let's proceed.

370
00:17:32,830 --> 00:17:34,900
We go to the next element which is five.

371
00:17:34,900 --> 00:17:38,530
Now we have to decide where to insert this five in the output array.

372
00:17:38,530 --> 00:17:41,410
So we're going to check over here five at index five.

373
00:17:41,410 --> 00:17:43,840
In the cumulative sum array the value is five.

374
00:17:43,870 --> 00:17:45,850
We decrement it by one we get four.

375
00:17:45,850 --> 00:17:50,350
And we are going to insert this five at index four in the output array which is over here.

376
00:17:50,350 --> 00:17:51,610
So this is index four.

377
00:17:51,610 --> 00:17:53,380
So let's insert five over here.

378
00:17:53,380 --> 00:17:54,490
Again we proceed.

379
00:17:54,490 --> 00:17:56,530
We come to the next element which is seven.

380
00:17:56,530 --> 00:18:01,300
And we check index seven in the cumulative sum array which is over here.

381
00:18:01,300 --> 00:18:03,760
And we're going to decrement this six by one.

382
00:18:03,760 --> 00:18:05,080
So this becomes five.

383
00:18:05,080 --> 00:18:09,070
And we are going to insert this seven at index five which is over here right.

384
00:18:09,070 --> 00:18:09,970
So that's over here.

385
00:18:09,970 --> 00:18:12,010
So let's insert seven over here.

386
00:18:12,010 --> 00:18:14,470
And yes you can see the elements.

387
00:18:14,470 --> 00:18:16,750
The digits over here are now sorted.

388
00:18:16,750 --> 00:18:19,150
So this is how the cumulative sort works.

389
00:18:19,150 --> 00:18:19,660
All right.

390
00:18:19,660 --> 00:18:24,280
Now let's take a look at an interesting property about the counting sort.

391
00:18:24,310 --> 00:18:27,400
Now the counting sort is stable.

392
00:18:27,400 --> 00:18:27,670
All right.

393
00:18:27,670 --> 00:18:29,500
So that's a very important property.

394
00:18:29,500 --> 00:18:30,940
Now what do we mean with this.

395
00:18:30,940 --> 00:18:31,210
All right.

396
00:18:31,210 --> 00:18:33,670
So let's try to understand what do we mean with this.

397
00:18:33,670 --> 00:18:38,740
Now again this is why this is the main reason why we go in this direction.

398
00:18:38,740 --> 00:18:42,370
Once we have created the cumulative sum and then decide where to insert it.

399
00:18:42,370 --> 00:18:43,810
So let's try to understand why.

400
00:18:43,810 --> 00:18:45,250
Let's take a look at the threes.

401
00:18:45,250 --> 00:18:46,780
We have two threes over here.

402
00:18:46,780 --> 00:18:49,150
So this is one three and this is the other three.

403
00:18:49,150 --> 00:18:51,430
So these are actually equal in value.

404
00:18:51,430 --> 00:18:57,490
But if you take a look at their positioning in the output array you can see that their relative positioning

405
00:18:57,490 --> 00:18:58,270
is maintained.

406
00:18:58,270 --> 00:19:03,160
That is this this pink three is coming before the violet three in the input array.

407
00:19:03,160 --> 00:19:04,690
And you can see in the output array.

408
00:19:04,690 --> 00:19:07,990
Also the pink three is coming ahead of the violet three.

409
00:19:07,990 --> 00:19:11,230
So if there is a tie that's what we mean with stable.

410
00:19:11,230 --> 00:19:16,420
If there is a tie between values the initial relative ordering is maintained.

411
00:19:16,420 --> 00:19:19,600
So that is why we are going in this direction right.

412
00:19:19,600 --> 00:19:21,760
So we encounter this three first.

413
00:19:21,760 --> 00:19:23,770
So that's why we are inserting it over here.

414
00:19:23,770 --> 00:19:28,870
Now if we had gone in this direction then we would have inserted this three at this position.

415
00:19:28,870 --> 00:19:30,910
And in that case it would not be stable.

416
00:19:30,910 --> 00:19:33,970
So that is the reason why we move in this direction.

417
00:19:33,970 --> 00:19:34,360
All right.

418
00:19:34,360 --> 00:19:40,330
Finally, when we are filling the output array and the reason why we can use counting sort for radix

419
00:19:40,330 --> 00:19:43,270
sort is because counting sort is stable.

420
00:19:43,270 --> 00:19:48,280
And again stable means in the case of a tie the initial relative ordering is maintained.

421
00:19:48,280 --> 00:19:48,790
All right.

422
00:19:48,790 --> 00:19:52,450
So we have got a good understanding about how the counting sort works.

423
00:19:52,450 --> 00:19:56,470
And we have seen how to sort numbers where we just had one digit.

424
00:19:56,470 --> 00:19:56,830
Right.

425
00:19:56,830 --> 00:19:59,980
So all the integers which was given to us in this in the input array.

426
00:20:00,160 --> 00:20:01,450
Just add one digit.

427
00:20:01,450 --> 00:20:04,510
So this is going to be used when we implement radix sort.

428
00:20:04,540 --> 00:20:10,870
Now before we go ahead and see how we can use the counting sort in the case of implementing radix sort,

429
00:20:10,870 --> 00:20:14,950
let's take a look at the complexity analysis of the counting sort.

430
00:20:15,400 --> 00:20:17,350
Now what is going to take time?

431
00:20:17,350 --> 00:20:19,990
First let's take a look at the time complexity.

432
00:20:19,990 --> 00:20:22,510
What all things over here is going to take time.

433
00:20:22,510 --> 00:20:29,290
Now over here you can see we have to loop through the input array and identify the frequencies.

434
00:20:29,290 --> 00:20:30,730
That's this step over here right.

435
00:20:30,730 --> 00:20:34,420
So that's going to be an O of N operation because why is that.

436
00:20:34,420 --> 00:20:36,520
So n is the number of elements in the input array.

437
00:20:36,520 --> 00:20:36,730
Right.

438
00:20:36,730 --> 00:20:42,220
So we have to go through the input array or iterate through the input array to be able to understand

439
00:20:42,220 --> 00:20:44,320
how many times each element is occurring.

440
00:20:44,320 --> 00:20:47,830
And to determine the frequency to fill in this array over here.

441
00:20:47,830 --> 00:20:49,720
So that's an O of n operation.

442
00:20:49,720 --> 00:20:53,290
And then we have to form the cumulative sum array.

443
00:20:53,290 --> 00:20:57,700
For this we have to just go through the array which we have formed over here.

444
00:20:57,700 --> 00:21:00,550
That is going to be an O of k operation.

445
00:21:00,550 --> 00:21:03,760
And again remember k is just the range of the digits right.

446
00:21:03,760 --> 00:21:08,680
So we have initially said that every digit will be in the range of zero to k.

447
00:21:08,680 --> 00:21:11,050
Or it can be 0 to 9.

448
00:21:11,050 --> 00:21:11,320
Right.

449
00:21:11,320 --> 00:21:14,140
So again that's that's that's the k over here.

450
00:21:14,140 --> 00:21:16,720
So this over here is going to be of the order of k.

451
00:21:16,720 --> 00:21:22,360
So looping through the array over here and formulating the cumulative sum array is going to be an O

452
00:21:22,360 --> 00:21:23,380
of k operation.

453
00:21:23,380 --> 00:21:25,270
And then we have the output array over here.

454
00:21:25,270 --> 00:21:25,450
Right.

455
00:21:25,450 --> 00:21:29,260
So we have the output array over here which is again going to be forming.

456
00:21:29,260 --> 00:21:33,970
The output array is going to be an O of n operation because we have to again loop through the input

457
00:21:33,970 --> 00:21:35,620
array to determine.

458
00:21:35,620 --> 00:21:40,900
And then we do some constant time operations to to determine where to insert it to the output array.

459
00:21:40,900 --> 00:21:47,620
So you can see the total time complexity of this solution is going to be of the order of n plus k.

460
00:21:47,620 --> 00:21:47,830
Right.

461
00:21:47,830 --> 00:21:51,160
Because we don't need to write two n plus k because that is the constant.

462
00:21:51,160 --> 00:21:55,120
So we can say the time complexity is of the order of n plus k.

463
00:21:55,120 --> 00:21:59,260
And again the unique values over here is in the range of zero to k.

464
00:21:59,260 --> 00:22:01,120
So that's how we get this k over here.

465
00:22:01,150 --> 00:22:03,340
Now what about the space complexity.

466
00:22:04,150 --> 00:22:06,190
When it comes to space complexity.

467
00:22:06,190 --> 00:22:09,220
Let's try to think what all takes extra space, right?

468
00:22:09,220 --> 00:22:11,500
So there is this array over here which we are forming.

469
00:22:11,500 --> 00:22:13,810
So let me just clean this up a little bit.

470
00:22:16,900 --> 00:22:17,290
All right.

471
00:22:17,320 --> 00:22:19,870
Now we have this array over here right.

472
00:22:19,870 --> 00:22:21,670
So that takes k space.

473
00:22:21,670 --> 00:22:25,420
And then we have this output array which again takes n space.

474
00:22:25,420 --> 00:22:31,180
So this over here takes k space because it's going to have elements of the order of k right.

475
00:22:31,180 --> 00:22:32,680
So it's zero to k.

476
00:22:32,680 --> 00:22:34,750
So we can say there are k plus one elements.

477
00:22:34,750 --> 00:22:36,310
But again that does not matter.

478
00:22:36,310 --> 00:22:37,660
One is just a constant.

479
00:22:37,660 --> 00:22:41,620
So the space that is consumed over here is going to be of the order of K.

480
00:22:41,620 --> 00:22:46,510
And then over here we have the output array which is going to take space of the order of n.

481
00:22:46,510 --> 00:22:52,030
So that's why we can say that the space complexity of the counting sort algorithm is of the order of

482
00:22:52,030 --> 00:22:53,050
n plus k.

483
00:22:53,620 --> 00:22:54,250
All right.

484
00:22:54,250 --> 00:23:00,850
Now again remember if k is uh when when we are dealing with decimal numbers we can just say that k is

485
00:23:00,850 --> 00:23:01,600
ten, right.

486
00:23:01,600 --> 00:23:04,750
Because the values is going to be from 0 to 9.

487
00:23:04,750 --> 00:23:05,050
Right.

488
00:23:05,050 --> 00:23:09,700
So in that case we can say k is equal to ten because we are dealing with base ten.

489
00:23:09,700 --> 00:23:10,450
All right.

490
00:23:14,080 --> 00:23:20,320
Now let's proceed and see how we can use the counting sort to implement radix sort.

491
00:23:20,320 --> 00:23:25,870
And the reason why we are using counting sort to implement radix sort is first that the counting sort

492
00:23:25,900 --> 00:23:29,740
is stable, and secondly, we are trying to get a good time complexity.

493
00:23:29,740 --> 00:23:30,160
All right.

494
00:23:30,160 --> 00:23:34,180
And we have seen the time complexity of the counting sort is O of n plus k.

495
00:23:34,180 --> 00:23:37,900
And if you are just dealing with decimal numbers k is going to be a constant.

496
00:23:37,900 --> 00:23:43,360
So we can just say that counting sort is achieving O of n time complexity, and any other good sort

497
00:23:43,360 --> 00:23:45,910
can not go beyond O of n log n.

498
00:23:45,910 --> 00:23:46,240
All right.

499
00:23:46,240 --> 00:23:48,220
So that's the reason why we are using counting sort.

500
00:23:48,250 --> 00:23:49,540
Now let's proceed.

501
00:23:49,540 --> 00:23:56,680
And let's see, let's say the numbers which we have to sort are these which is three 8473, 374, one

502
00:23:56,680 --> 00:24:00,010
8365, 247 and 185.

503
00:24:00,010 --> 00:24:06,070
Now what we will do is, as we have seen in part one, we are only going to take the units digits over

504
00:24:06,070 --> 00:24:11,200
here, which is four, three, four and three, five, seven and five.

505
00:24:11,200 --> 00:24:15,100
Now we are going to sort these numbers based on their units digit.

506
00:24:15,100 --> 00:24:16,960
So that's how we are going to do this.

507
00:24:16,960 --> 00:24:22,180
Now for sorting the numbers based on their units digits we are going to use counting sort.

508
00:24:22,180 --> 00:24:24,550
So let's again trace the algorithm.

509
00:24:24,550 --> 00:24:28,630
So over here I have an array with indices from 0 to 9.

510
00:24:28,630 --> 00:24:34,690
Because we know that because this is in decimal system, every digit in the units digit in the units

511
00:24:34,690 --> 00:24:37,210
place can only be among 0 to 9.

512
00:24:37,210 --> 00:24:40,930
So that's why I have this array with the indices from 0 to 9.

513
00:24:40,930 --> 00:24:41,350
All right.

514
00:24:41,380 --> 00:24:43,480
Now let's go ahead and fill in the frequencies.

515
00:24:43,480 --> 00:24:48,670
So you can see that we have two fourths and we have two threes one.

516
00:24:48,670 --> 00:24:51,010
And then we have two fives and one seven.

517
00:24:51,010 --> 00:24:52,360
So this is the frequency.

518
00:24:52,360 --> 00:24:55,360
And then everywhere else we are just going to fill in with zero.

519
00:24:56,260 --> 00:24:56,710
All right.

520
00:24:56,740 --> 00:24:59,770
Now we are going to create the cumulative sum array.

521
00:25:00,490 --> 00:25:03,040
Again it's going to have indexes from 0 to 9.

522
00:25:03,040 --> 00:25:05,770
And then we just fill the cumulative frequencies.

523
00:25:05,770 --> 00:25:06,430
So you can see.

524
00:25:06,430 --> 00:25:08,080
So over here you just have zero.

525
00:25:08,080 --> 00:25:11,620
And then for this value you have to add these two.

526
00:25:11,650 --> 00:25:13,030
So you get zero itself.

527
00:25:13,030 --> 00:25:15,550
Now when we add these two you get value zero itself.

528
00:25:15,550 --> 00:25:18,820
Over here you add these two you get two over here you add these two.

529
00:25:18,850 --> 00:25:21,970
You get four over here for two plus two gives you six.

530
00:25:21,970 --> 00:25:28,810
Six plus zero is six six plus one is seven and seven plus zero is seven and seven plus zero is again

531
00:25:28,810 --> 00:25:29,140
seven.

532
00:25:29,140 --> 00:25:31,750
So that's how we get the cumulative sum array over here.

533
00:25:31,750 --> 00:25:32,050
All right.

534
00:25:32,050 --> 00:25:33,850
Now let me just clean this up.

535
00:25:33,850 --> 00:25:37,180
Now what we will do is we will have our output array over here.

536
00:25:37,900 --> 00:25:43,300
And we are having the indexes over here zero one, two, three, four, five and six.

537
00:25:43,300 --> 00:25:44,950
And then we go bottom up right.

538
00:25:44,950 --> 00:25:46,750
So we start from 185.

539
00:25:46,750 --> 00:25:48,490
So we go in this direction.

540
00:25:48,490 --> 00:25:51,310
We have seen this is important to keep the stability.

541
00:25:51,310 --> 00:25:54,460
Now the first digit over here is five.

542
00:25:55,200 --> 00:26:00,030
Now we have to decide where should we insert 185 in the output array?

543
00:26:00,030 --> 00:26:01,530
Which is this over here right now.

544
00:26:01,530 --> 00:26:04,290
For this we will take a look at the index five.

545
00:26:04,290 --> 00:26:05,730
In the cumulative sum array.

546
00:26:05,760 --> 00:26:07,230
The value over here is six.

547
00:26:07,230 --> 00:26:09,360
So we reduce this by one.

548
00:26:09,780 --> 00:26:11,310
So we get five over here.

549
00:26:13,220 --> 00:26:17,450
And hence we are going to insert 185 at index five.

550
00:26:17,480 --> 00:26:17,750
All right.

551
00:26:17,750 --> 00:26:18,380
So let's do that.

552
00:26:18,380 --> 00:26:20,150
So we get 185 over here.

553
00:26:20,180 --> 00:26:21,350
Now we proceed.

554
00:26:21,350 --> 00:26:23,570
We take the next digit which is seven.

555
00:26:23,570 --> 00:26:27,440
Now for this we have to decide where to insert this 247.

556
00:26:27,440 --> 00:26:29,600
So we take a look at this seven over here.

557
00:26:29,600 --> 00:26:32,900
So the value over here is seven which is reduced by one.

558
00:26:32,900 --> 00:26:33,800
So we get six.

559
00:26:33,800 --> 00:26:37,970
Now we are going to insert 247 at index six which is over here.

560
00:26:39,450 --> 00:26:42,480
Now we proceed to the next digit is five right.

561
00:26:42,480 --> 00:26:43,260
This is five.

562
00:26:43,260 --> 00:26:45,030
So again we take a look at this five.

563
00:26:45,030 --> 00:26:47,040
Over here we decrement this by one.

564
00:26:47,040 --> 00:26:47,970
So we get four.

565
00:26:47,970 --> 00:26:51,480
And this 65 is going to be inserted at index four.

566
00:26:51,480 --> 00:26:52,530
Again we proceed.

567
00:26:52,530 --> 00:26:54,000
So over here we have three.

568
00:26:54,000 --> 00:26:55,980
And we take a look at index three.

569
00:26:55,980 --> 00:26:58,110
So the value is two we subtract by one.

570
00:26:58,110 --> 00:26:59,070
So we get one.

571
00:26:59,070 --> 00:27:03,270
And we are going to insert 183 at index one which is over here.

572
00:27:03,270 --> 00:27:04,320
Now we proceed.

573
00:27:04,320 --> 00:27:05,970
The next value over here is four.

574
00:27:05,970 --> 00:27:08,400
So we take a look at index four which is over here.

575
00:27:08,400 --> 00:27:11,160
Now we decrease the value by one which is three.

576
00:27:11,160 --> 00:27:14,400
So we're going to insert 374 at index three.

577
00:27:14,520 --> 00:27:15,540
Again we proceed.

578
00:27:15,540 --> 00:27:16,800
So over here we have three.

579
00:27:16,800 --> 00:27:19,680
So we are taking a look at index three where the value is one.

580
00:27:19,680 --> 00:27:20,850
So we decrease this.

581
00:27:20,850 --> 00:27:22,320
So we get zero over here.

582
00:27:22,320 --> 00:27:25,380
And hence we are going to insert 73 at index zero.

583
00:27:25,380 --> 00:27:27,390
And then we have 384.

584
00:27:27,420 --> 00:27:28,770
The value over here is four.

585
00:27:28,770 --> 00:27:30,300
So we take a look at index four.

586
00:27:30,300 --> 00:27:31,620
Over here the value is three.

587
00:27:31,650 --> 00:27:34,650
We reduce this by one so we get two.

588
00:27:34,680 --> 00:27:38,010
Hence we are going to insert 384 at index two.

589
00:27:38,040 --> 00:27:41,340
Now you can see we have done one time the counting sort.

590
00:27:41,370 --> 00:27:41,760
Right.

591
00:27:41,760 --> 00:27:44,580
And that's done based on the units digits.

592
00:27:45,180 --> 00:27:45,570
All right.

593
00:27:45,600 --> 00:27:51,090
Now what we will do is we will again sort these numbers based on their ten's digits which is these digits.

594
00:27:51,090 --> 00:27:51,510
Right.

595
00:27:51,510 --> 00:27:53,880
Again we will implement the counting sort for this.

596
00:27:53,880 --> 00:27:57,300
And when we do this the numbers will look like this.

597
00:27:57,300 --> 00:28:03,300
And after this finally we will again implement counting sort on the digits in the hundredths place,

598
00:28:03,300 --> 00:28:05,100
which is what we have over here.

599
00:28:05,100 --> 00:28:08,040
And when we do that again we will get the numbers like this.

600
00:28:08,040 --> 00:28:09,240
And that's the end, right?

601
00:28:09,240 --> 00:28:14,220
So we just had to do it three times because the maximum digit over here is one hundredths place.

602
00:28:14,220 --> 00:28:16,290
And then you can see the numbers are sorted.

603
00:28:16,290 --> 00:28:22,020
We have 6573 183 185 247 374 and 384.

604
00:28:22,020 --> 00:28:23,280
And this is sorted.

605
00:28:23,280 --> 00:28:26,100
So this is how radix sort is implemented.

606
00:28:26,100 --> 00:28:30,300
And you can see that we are using counting sort to implement the radix sort.

607
00:28:30,300 --> 00:28:36,930
And we can implement the counting sort because we know that the value at at the, at a particular place,

608
00:28:36,930 --> 00:28:43,040
whether the units place or the tenths place or the hundredths place, etc., will lie between 0 and

609
00:28:43,040 --> 00:28:43,410
9.

610
00:28:43,410 --> 00:28:48,510
So because we know that we can use the counting sort and we have, we have seen that in the case of

611
00:28:48,510 --> 00:28:53,010
decimal values, this is getting a time complexity of o of n.

612
00:28:53,010 --> 00:28:58,470
Now again, an interesting thing to notice over here is the counting sort works because it's stable.

613
00:28:58,470 --> 00:29:02,490
For example, you can see over here we have 374 and 384.

614
00:29:02,490 --> 00:29:05,130
Now both of them have the hundredths place three.

615
00:29:05,130 --> 00:29:05,490
Right.

616
00:29:05,490 --> 00:29:13,050
So because the counting sort is stable in the case of a tie it will maintain or preserve the previous

617
00:29:13,050 --> 00:29:13,500
order.

618
00:29:13,500 --> 00:29:17,910
So that's why you can see that over here you have 374 before 384.

619
00:29:17,910 --> 00:29:19,500
Because that's the order over here also.

620
00:29:19,500 --> 00:29:19,830
Right.

621
00:29:19,830 --> 00:29:22,110
We have 374 before 384.

622
00:29:22,110 --> 00:29:24,420
Hence the order that is preserved.

623
00:29:24,420 --> 00:29:24,690
Right.

624
00:29:24,690 --> 00:29:26,250
The previous order is preserved.

625
00:29:26,250 --> 00:29:30,300
And over here you can see we have 374 and 384.

626
00:29:30,300 --> 00:29:30,930
All right.

627
00:29:31,410 --> 00:29:34,860
So the counting sort is stable is a stable sort.

628
00:29:34,860 --> 00:29:39,270
And that's why we are using the counting sort for implementing the radix sort.

629
00:29:39,300 --> 00:29:44,400
Now let's take a quick look at the time and space complexity of the radix sort.

630
00:29:44,430 --> 00:29:50,820
Now previously we have seen that in the case of counting sort, the time complexity is O of n plus k

631
00:29:50,820 --> 00:29:52,110
space and time.

632
00:29:52,110 --> 00:29:52,530
Right.

633
00:29:52,530 --> 00:29:57,000
And in the case of decimals that would be o of n plus ten and ten is a constant.

634
00:29:57,000 --> 00:29:58,110
So we can just avoid it.

635
00:29:58,110 --> 00:30:00,870
And we can say it's O of n space and time.

636
00:30:00,870 --> 00:30:02,370
Now let's proceed.

637
00:30:02,370 --> 00:30:03,690
What about radix sort?

638
00:30:03,690 --> 00:30:05,790
What would be its time complexity?

639
00:30:05,790 --> 00:30:12,870
We can see that we have to implement the counting sort d number of times, where d is the maximum number

640
00:30:12,870 --> 00:30:16,620
of digits in any of the uh given numbers in the array.

641
00:30:16,650 --> 00:30:17,100
All right.

642
00:30:17,100 --> 00:30:19,110
So d is the largest number of digits.

643
00:30:19,110 --> 00:30:23,280
So we can say that the time complexity is d times n plus k.

644
00:30:23,280 --> 00:30:24,810
So that's the time complexity.

645
00:30:24,810 --> 00:30:28,470
And again if the base is ten we know that d is just ten.

646
00:30:28,470 --> 00:30:30,120
And that's a constant.

647
00:30:30,120 --> 00:30:31,170
So we can avoid it.

648
00:30:31,170 --> 00:30:35,190
And we can say that the time complexity is O of d into n.

649
00:30:35,190 --> 00:30:40,890
And if we know D like for example, in this case, if we know that d is equal to three, we could even

650
00:30:40,890 --> 00:30:41,520
avoid that.

651
00:30:41,520 --> 00:30:44,520
And we can say that the time complexity is O of n.

652
00:30:44,520 --> 00:30:50,760
But then generally we can just say the time complexity is O of d into n in the case of decimal values.

653
00:30:50,760 --> 00:30:52,860
Now what about the space complexity?

654
00:30:52,860 --> 00:30:57,300
The space complexity is going to be o of n plus k itself, right.

655
00:30:57,300 --> 00:30:57,930
Why is that.

656
00:30:57,930 --> 00:31:00,240
So you can see we consume extra space.

657
00:31:00,240 --> 00:31:02,880
But that is only while doing the counting sort.

658
00:31:02,880 --> 00:31:07,140
So we don't need to keep, uh, keep using that space which is used.

659
00:31:07,140 --> 00:31:09,480
For example we are doing counting sort one time over here.

660
00:31:09,480 --> 00:31:11,100
So we have an extra array.

661
00:31:11,100 --> 00:31:16,320
We have the auxiliary array, the cumulative sum array etc. but then that is no longer required when

662
00:31:16,320 --> 00:31:18,090
we are doing the second counting sort.

663
00:31:18,090 --> 00:31:19,920
So we can free up this space.

664
00:31:19,920 --> 00:31:25,500
So that's why the space complexity of the radix sort and the counting sort is the same, which is O

665
00:31:25,500 --> 00:31:26,520
of n plus k.

666
00:31:26,520 --> 00:31:30,270
And in the case of decimal values we know k is equal to ten.

667
00:31:30,270 --> 00:31:34,770
So we can say that the space complexity over here is also o of n.

668
00:31:34,770 --> 00:31:38,850
So the time complexity is of the order of d into n plus k and.

669
00:31:38,990 --> 00:31:42,020
And the space complexity is of the order of n plus k.

670
00:31:42,500 --> 00:31:47,690
Now, an interesting thing to notice over here is that let's say we increase k right?

671
00:31:47,690 --> 00:31:50,930
Let's say we increase k then d would decrease.

672
00:31:50,930 --> 00:31:52,610
Let's try to understand what this means.

673
00:31:52,610 --> 00:31:55,520
Now for example let's say we have the binary.

674
00:31:55,520 --> 00:31:57,170
Let's say we have the decimal system.

675
00:31:57,170 --> 00:32:01,520
So let's say k is equal to ten because we have the digits from 0 to 9.

676
00:32:01,520 --> 00:32:08,240
Right now if we take into consideration the binary system k is equal to two because we only have zeros

677
00:32:08,240 --> 00:32:08,810
and ones.

678
00:32:08,810 --> 00:32:12,410
Right now if we want to express a number 50.

679
00:32:12,410 --> 00:32:17,090
For example, in the decimal system you can see we are using only two digits.

680
00:32:17,090 --> 00:32:25,730
But if we want to express the same 50 in the binary system, you can see that we would have to use 110010.

681
00:32:25,730 --> 00:32:29,630
So you can see that more digits are used when k is less.

682
00:32:29,630 --> 00:32:35,780
Or you can say when k is increased from 2 to 10 the number of digits is reducing.

683
00:32:35,780 --> 00:32:35,960
Right.

684
00:32:35,960 --> 00:32:39,500
So over here you have 1234566 digits.

685
00:32:39,500 --> 00:32:42,200
But that is reducing to two over here.

686
00:32:42,200 --> 00:32:45,170
So that's why when you increase k d decreases.

687
00:32:45,170 --> 00:32:47,420
Again this is just an interesting observation.

688
00:32:47,420 --> 00:32:47,900
All right.

689
00:32:47,900 --> 00:32:50,000
So over here d was equal to two.

690
00:32:50,000 --> 00:32:51,770
And over here D is equal to six.

691
00:32:51,770 --> 00:32:51,950
Right.

692
00:32:51,950 --> 00:32:55,130
So when you increase k d is getting reduced.

693
00:32:55,930 --> 00:32:56,260
All right.

694
00:32:56,260 --> 00:32:58,120
So that's what we've seen over here.

695
00:32:58,120 --> 00:33:00,910
We have increased it to ten and D is reduced to two.

696
00:33:00,940 --> 00:33:06,400
So basically if you do that so what's the implication on the time and space complexity.

697
00:33:06,400 --> 00:33:11,200
We can see that when we're increasing k the space complexity is increasing right.

698
00:33:11,200 --> 00:33:13,270
Because this is over here this increases.

699
00:33:13,270 --> 00:33:18,400
But then when we increase k d decreases this decreases.

700
00:33:18,400 --> 00:33:22,090
And hence the overall time complexity will reduce.

701
00:33:22,090 --> 00:33:25,090
So it's basically a trade off between time and space.

702
00:33:25,090 --> 00:33:30,970
Whether we have to implement something in a in the binary system or where when, whether we have to

703
00:33:30,970 --> 00:33:33,190
use numbers in the decimal system, etc..

704
00:33:33,190 --> 00:33:35,050
So this is just an interesting observation.

705
00:33:35,050 --> 00:33:35,290
All right.

706
00:33:35,290 --> 00:33:37,840
So if we increase k the space increases.

707
00:33:37,840 --> 00:33:43,030
But in general we have already seen that the time complexity is O of d into n plus k.

708
00:33:43,030 --> 00:33:46,420
And the space complexity is O of n plus k.