Welcome back.
Let's now go ahead and implement the radix sort, which we discussed in the previous video.
For this we are going to write a function.
And let's call this function radix sort itself.
Now this function is going to take in the array of integers which is given to us.
So remember this array over here consists only of positive integers.
Now if you have to do radix sort on an array of integers where negative numbers are also there, we
have to do it in a different way.
So over here in the question it's mentioned that the integers are positive.
Now let's go ahead.
Now first let's check if the array is empty.
So if array dot length is equal to zero then we can just return.
And let's say we return a message saying the array is empty.
All right.
Now, if this is not the case, let's proceed further.
So we have to first identify what is the maximum number of digits which is present in any integer which
is given to us in the array.
So for this let's first identify the greatest number.
So we can say const greatest number in the array which is given to us is equal to math dot max.
And then we will use the spread operator array.
So this will give us the greatest number in the array which is given to us.
Now let's go ahead and find the number of digits in the greatest number.
Now let's have a quick side note over here and let's see how we can implement this.
So let me grab a pen for this.
All right.
So we are back.
So let me just show you the logic that we will use to find the number of digits in the greatest number
which we have identified over here.
Now if we take a, a number and then if you take the log to the base ten for that number.
So let's say log of a number, let's say 100.
And this is to the base ten.
Now typically whenever we have seen log so far in the course and even in the remaining videos, we will
be doing log to the base two.
Now over here, just because we have to find the number of digits we will be using, log to the base
ten.
So log to the base ten of 100 will be equal to two.
Again, remember the definition of this is just the same.
This to two over here is actually ten, which is the base to what power will give this 100 over here,
which is equal to two.
Now log 100.
When we take to the base ten will be equal to two.
Similarly log ten to the base ten will be equal to one because ten to the power one is equal to ten.
And if you take log 1000 to the base.
Then you will get the value as three, because ten to the power three is equal to this thousand over
here.
Now we will use this property to find the number of digits.
So let's take a look.
Now if you take any number let's say you have the number two three, four.
And you want to know how many digits are there in this number.
So if you take log 234 to the base ten we will get a value which is in between 2 and 3.
Because you can see that for log 100 the value is two and log for log 1000 the value is three.
So whatever we are getting over here is going to be some decimal.
So it's going to be two point something.
All right.
So if we take this value and if we floor this so we will get two right.
So if we floor this we will just get two.
And then we just have to add one to it.
And you can see that we are getting three which is the number of digits over here.
So this is how we will find the number of digits.
So let's just quickly see this one more time.
So what we are going to do is let's say the greatest number is 1746.
In the array of integers which is given to us.
So we will find the log of this number to the base ten.
All right.
Now the interesting thing to notice is that for log 1000.
To the base ten, the value is equal to three, and for log 10,000.
To the base ten.
The value is going to be four.
Now 1007 46 is between 1000 and 10,000.
So this value over here is going to be three point something.
So it's going to be a decimal.
So we are going to floor this.
So when we floor this we will get the value three.
And then we will add one to it to get the number of digits which is four over here.
So let's go ahead and implement this in the code.
All right.
So we can say const number of digits.
Is equal to math dot floor.
And then inside this we're going to take the logarithm of the greatest number to the base ten.
So we can say math dot log to the base ten.
Of the greatest number, which is what we have found over here.
All right.
So we are taking the logarithm of the greatest number to the base ten.
And then we are flooring it.
And then we just have to add one to it.
So this will give us the number of digits in the greatest number.
So this is the number of times that we have to do the counting sort.
So let's just write a comment over here.
So the counting sort.
Has to be done.
X number of times.
Where x is equal to the number of digits which we just now found.
So this is now what we have to implement.
So let's go ahead.
So let's say for let I is equal to zero I less than number of digits.
I plus, plus.
All right.
And inside this for loop we are going to call the counting sort function, which we have to go ahead
and write.
So we can say counting sort.
And we will just pass in the array and we will pass in I to know at what place or whether we are we
are doing the counting sort for the ones digits, the tens digits or the hundreds digits, etc. so that's
why we have to pass.
I also and then once this is done, we can just return the array and that would be the sorted array.
So this is how we will implement this.
Now let's go ahead and write the counting sort function which we are calling over here.
So we can say function or let's say const.
Counting sort.
Is equal to function.
And this takes in the array.
And let's say we call the second, uh, parameter over here place to because it indicates whether we
are doing counting sort on the ones place or the tens place, etc..
All right.
So let's go ahead.
Now first let's have an output array.
We can say const output.
Is equal to new array.
And this array is going to be of length equal to the length of the array which is given to us.
So that's array dot length.
And then let's just fill every value in this output array with zero.
So fill zero.
Now let's go ahead and have a temporary array where we will count the number of times that each digit
occurs.
And remember, every digit is going to be between 0 and 9 because this is the decimal system.
So we have const temp and there are only ten possible values.
So this array is going to be of length ten right.
Because the possible values are 0 to 9.
So new array of length ten.
And let's just fill every place in this array also with zero.
Now let's go ahead and identify the digit place.
So let's have a side note and understand what we're trying to do over here.
We are going to identify a method by which we can just isolate the digit that we need from the integer.
All right.
So again this array is going to have the various integers.
Now let's say one of the integers is 241.
Now when we are implementing counting sort on the ones place, we will only want the digit one.
Right now, when we are implementing the counting sort on the tens place, we will only want the digit
four.
And similarly, when we are implementing the counting sort on the hundreds place, we will only want
the digit two.
So let's see how we can do this.
Now for this, let's say first we want the units place which is one.
So what we will do is let me just change the color of the pin.
So what we will do is we will do 241 and then we will just take the mod of ten of this.
All right.
So that means we will divide 241 with ten and take the remainder.
So 241 divided by ten gives the remainder remainder as one which is this digit over here.
So that's how we will get one.
Now let's say we want four.
So let's see what we can do.
So first what we will do is we will take 241 and we will divide 241 with ten.
So when we divide two 241 with ten and then we are flooring it.
When we do this, we will get 24.
Now on 24, we will do the same thing.
That is, we will take mod of ten.
All right.
So this will give us the remainder when 24 is divided by ten which is equal to four.
And similarly when we want to in this case what we will do is we will take 241 and we will divide it
with 100.
All right.
So in this case it was ten.
Over here we are dividing it with 100.
And then we will floor it.
So when we do 241 divided by 100 and then when you're flooring it, we will get two, and then we will
just do the same thing.
That is we are going to do percentage ten.
And this will give us the remainder when two is divided by ten which is two itself.
And that's how we will get this digit right.
So this is what we are going to implement.
Now notice that percentage ten is the same across right.
So over here also we have percentage ten over here.
Also we have percentage ten.
And over here also we have the same thing.
So we are using the modulo operator.
Now what is changing is in this case 241 is divided with ten to the power zero.
Which is one.
In this case, we are dividing 241 with ten to the power one, and in this case we are dividing 241
with ten to the power two, which is 100.
Right.
And again, notice over here, when we are calling the counting sort function, let's say the number
of digits is maximum three.
So the values that I will take is zero one and two.
And we are passing these values also.
So when we want the units digit we just have to raise ten to the power zero which is I itself.
When we want the 10th digit we have to just raise ten to the power I, which is one.
And similarly, when we want the hundredths digit we have to raise for the denominator, I'm saying
we have to just raise ten to the power two, which is also the value of I.
So let's go ahead and implement this in our code.
And so again remember this is to get the particular digit that we need because we are implementing the
counting sort first on the units digits and then on the tenths digits and then on the hundredths digits
and etc..
So let's go ahead and implement this now.
All right.
Now to know by what I have to divide the particular integer.
Let's have a variable.
Let's call it digit place.
Because that will depend on what place or whether it's once digits or tens, digits or hundreds, digits,
etc. that we are sorting.
So that's why I'm calling it digits place over here.
Now let's proceed.
So we have digits place over here.
And again remember when I was equal to zero we had to divide by ten to the power zero.
When I was equal to one we had to divide by ten to the power one.
So digit place is just going to be math dot pow.
Ten comma AI.
That means we are going to raise ten to the power I.
Now when we are sorting the units place, I is going to be zero.
And when we are sorting the tens place, I is going to be one, etc..
So we get the digit place over here.
Now what we will do is let's go ahead and loop through the numbers in our array and let's, uh, fill
out what the frequency of the digits is.
And accordingly we are going to change the temp array.
So we have discussed this in the concept video.
So let's go ahead and uh get the correct frequencies into the temp array.
So for this let's say for let num of array.
So we are taking each integer at a time, and then we are going to find the respective digit.
So let's say let digit is equal to math dot floor.
And then we are doing numb divided by digit place.
All right.
And after doing this, after doing the division and then after flooring this, what we will do is we
will just take percentage of ten.
Or modulo ten.
Right.
So we are getting the remainder.
So this is how we are going about with this.
So we do num divided by digit place.
And then we floor it and then we take percentage ten.
So that's what we just now discussed.
So this will give us the particular digit.
So again remember if the number is 241 for example when we are sorting the units digits this will give
us one.
When we are sorting the sorting according to the tenths digits.
This operation over here will give us four, etc..
So that is what we have done over here.
Now let's proceed.
Now we know the digit.
Now we are going to increase the count in the temp array at the digit index at index equal to digit.
So we can say temp at digit.
Plus plus.
All right.
So this will give us the array.
And now what we have to do is we have to take the cumulative sum for this.
Right.
So let's go ahead and do that.
So for let I is equal to zero.
I less than ten I plus plus and oh here we have ten because our temp array is of size ten right.
Only values from 0 to 9 can be there over here because this is in decimal system.
And then we just say temp at I is going to be equal to temp at I.
Temp at I minus one.
All right.
So this will give us the cumulative sum in the temp array.
And now we just have to go ahead and go from in the reverse direction.
Right.
So we have seen that we have to go and in the reverse direction.
So we will loop through the array which is given to us in the reverse direction.
And then we will find the digit based on whether we are sorting based on one digit, etc. we will take
the digit, and then we will decrement the count in the temp array for that particular index and take
the value after decrementing it.
So that's going to be the insert position.
And at that position in the output array we will insert the value which is there in the array which
is given to us.
So that's how we're going to implement this.
So let's go ahead and write this in code.
And again remember this is what we discussed in the concept video.
So if you feel confused with this do try to see that one more time.
Now let's go ahead and implement this.
So we're going from the back to the front.
So let J equal to array dot length minus one which is the last index.
And this will keep looping as long as j greater than equal to zero.
And then we do j minus minus.
Now once inside the for loop what we will do is first we have to find the current digit.
So let's say current digit.
So we have a variable.
Now this is going to be equal to math dot floor.
Aria j, which is the value.
Divided by digit place.
And then we are just going to take percentage ten.
Alright, so it's the same thing.
So we are taking the integer and then we are dividing it with digit place and we are floating it.
All right.
And once we have floated it we are going to take percentage ten.
So that will give us the respective digit.
Again it the digit that we want will depend on whether we are sorting based on the ones digit or the
tens digits or the hundredths digits, etc..
So once we get the digit, we are going to decrement the value in the temp array at index current digit.
So temp at current digit minus minus.
Now we have some value in the temp array at digit.
So that is going to be the index in the output array where we want to insert the value that is array
at j.
So let's just have one more variable to make the code more readable.
So let's say let insert position.
Is equal to temp at current digit.
So this is going to be the position where we want to insert the value in the output array.
So again we can use const over here.
And over here also we can use const.
Now, once we have identified the insert position, let's just say output at insert position.
Is equal to area J.
And that's it.
All right.
So that's it.
So by by this we will have completed the counting sort for the ones digit or hundredths digits or 10th
digit whatever based on one call.
Right.
So we are going to call this function the number of times x x number of times where x is equal to the
number of digits.
So in one time we are going to sort it either once based on one's digit or ten's digits or hundredths,
digits, etc..
So that's it.
Now all we have to do is we have to loop through the output array, and then we have to change the array
which is given to us so that the output array is copied into the array which is given to us.
So let's go ahead and do that.
So for let's say for let again I is equal to zero I less than output dot length.
I plus plus.
And then we can just say array at I is equal to output.
At I and that's it.
All right.
So this will keep this will modify the array so that the, the the order changes as per the output that
we have built over here the output array.
All right.
Now let's go ahead and test this function.
So let's call the radix sort function.
And let's have some sample input.
Let's pass in an array over here.
So let's say we are passing the values 380.
Or then we have, let's say 73, 374, then 183 and 65 and 247 and 185.
So let's go ahead and run the code and see what we're getting.
All right.
So let's take a look.
Right.
So we have an error.
Let's take a look at that.
So okay so this should be place.
It's not I it's place.
So over here we have an error because we are saying temp at I is equal to temp at I plus temp I minus
one.
So we cannot start at index zero.
It has to be index one right.
So let's now go ahead and try again.
Now yes you can see it's working.
So this was the array which was given to us.
And you can see it's sorted.
We have 6573 183 185 247 374 and 384.
Now let's take this input.
So this array over here and let's just walk through the code and see what's happening over here to understand
the code in a better manner.
Now let me just write this array over here and then we will just walk through it.
So we have 384.
And then we have 73.
And then we have 374.
And 183.
65.
247.
And 185.
Now let's see what's happening over here.
We are calling the radix sort function.
Now we come inside over here and we see that the array is not empty.
Then we find the greatest number.
So this over here we will find the greatest number.
So among all of these the greatest number is 384.
And then over here we will find the number of digits.
So we are going to take log ten of this.
Right.
So we have seen that log 100 is two.
And for log 1000 we will get three.
So when we do log 384 to the base ten we will get two point something.
And when we floor this we will get two.
And then we are just adding one.
So this is going to give us the number of digits as three.
All right.
So we have found that the number of digits is equal to three.
So we have to call the counting sort function three times.
Now let's go ahead.
So I is going to be zero then one and then two because number of digits is three.
So first we call the counting sort function the helper function.
And we pass in this array.
And I is going to be equal to zero.
Now let's walk through this.
So let's do it for zero.
And then it will do the same thing for the other places as well.
So initially place is zero and the array is passed over here.
Now let's see what's happening in the counting sort function.
So let's just clear this up.
All right.
Now we are inside the counting sort function.
Now, what we're doing is we are going to have this output array.
So this is going to be of the same length.
And we are filling every position with zero.
So our output array is going to look like this.
All right.
So this is the output array.
And then we are going to have a temp array which is of length ten.
So let's just have this over here.
So this is our temp array.
So 012, three four, five, six, seven, eight and nine.
So because we are having numbers in the decimal system, so every digit can only be from 0 to 9.
So that's why the temp array is of length ten.
And then we are filling everything with zero.
So we are having zero everywhere over here.
Then we come over here and we are going to find digit place.
So again we have seen that this is to find the respective digit.
Right.
So let's just walk through and see what's happening.
So at this point place is zero right.
So when we call the function place was zero.
So we are going to take ten to the power zero.
So ten to the power zero is going to be equal to one.
So digit place is one over here.
Now we are looping through the array which is given to us.
So initially we are taking num as 384.
And we are finding digit which is math.floor.
And we are dividing num by digit place.
So 384 is going to be divided by one.
So that's 384 itself.
And then we are doing percentage ten.
So that will give us the remainder when 384 is divided by ten which is equal to four.
So digit is going to be equal to four.
Now we are going to increment the value in the temp array at index four which is over here.
So this is going to be equal to one.
Now let's continue.
We take the next value from the array which is 73.
And then we are going to find the digit.
So 73 divided by one is 73 itself.
And then we do percentage ten.
So that gives us three and then temp at three plus plus.
So that's this over here.
So this becomes one.
Now we go to 374.
So again digit will be four and temp at four will be incremented.
So this becomes two.
And then we take the next value 183 digit will be equal to three.
So at three we are going to increment this.
So we get two over here.
And then we take 65.
So the digit is going to be five.
And then we increment this.
So this is going to be one.
Then 247 digit is going to be seven.
So we increment this to one.
And then we have 185 digit is going to be five.
So this is going to change to two.
So this is how our temp array looks like after this for loop.
Now we come over here and we are going to find the cumulative sum.
So again we have the same temp array.
What we are doing is temp at I is temp at I plus temp at I minus one.
And we are starting with I is equal to one.
So temp at one is going to be tempered one plus temp zero which is zero itself.
Now temp two is going to be tempered two plus tempered one which is zero itself.
Now temp at three is going to be tempered three plus temp at two which is two itself.
Now temp at four is going to be tempered four plus tempered three which is two plus two.
So this value over here changes to four.
And temp at five is going to be two plus four.
So this becomes six, and at six it's going to be six plus zero.
This zero over here which is six itself.
Now temp at seven is going to be this one plus six.
So this becomes seven.
And then over here also we have seven.
And over here also we have seven because these are just zero.
So this is how our temp array looks after this for loop.
Now after this we come over here we come to this for loop.
So we are starting with j equal to r I dot length minus one.
So the length over here is 34567.
So seven minus one J is going to start with six.
So that's index six over here right this one.
So we take this value over here 185.
And then we find the current digit which is 185 divided by one.
So this is 185 divided by one because digit place at this point is one right.
So in the next iteration it will be ten.
So over here it's one.
So 185 by one gives 185 itself.
And then we do percentage ten.
So that that gives us five.
So current digit is going to be equal to five.
And then temp at five we do minus minus.
So let's do that.
So temp at five we have six.
So we're going to decrement this to five.
And then the insert position is going to be temp at current digit which is five right.
So at five in the output array.
So this is our output array at index five we are going to insert array at j which is 185.
So 012345.
So this is five index five.
Over here we are going to have 185.
And then we again proceed to the next number, which is 247.
So let's go ahead and complete this iteration.
So 247 we find current digit.
So current digit is going to be seven.
And we come to the temp array at index seven we have the value seven.
So we decrement this to six.
Now at index six in the output array we are going to insert 247.
So 0123456.
So that's over here.
And we are going to insert 247 over here.
And then we again continue.
We come to 65 and digit is going to be five.
So we come over here at index five we have the value five.
We decrement this to four.
And then at index four in the output array we will insert 65.
So 01234.
That's over here.
So we are going to insert 65 over here.
And then we come to 183.
Current digit is going to be three.
So we come over here at index three we have two.
So this is going to be decremented to one.
So at index one we will insert the next value which is 183.
So zero one.
So over here we will insert 183.
Again, we continue.
We come to 374.
The digit is going to be four, right?
The current digit is going to be four.
And then at index four we have the value four.
This is going to be decremented.
So we get three over here.
Now at index three in the output array we will insert the value which is 374.
So 0123.
So over here we are going to insert 374.
Again we continue.
We come to 73.
Current digit is going to be equal to three.
At three we have one.
So we decrement this.
So we get zero over here.
And at index zero in the output array we will insert 73.
So 73 comes over here.
And then we come to 384.
Right.
So 384 the unit digit is four.
So current digit is going to be four.
So we come to four we decrement this.
So we get two.
So at index 2012 we will insert 384.
So that's it.
So once this is done.
Uh, that's that's how the output array would look at the end of this for loop.
Then we come over here and over here we are just going to loop through this array and change the array
over here.
This array over here is going to be changed to this array which we have just built.
So after this is over.
After this is over, this array over here which we started with is going to look like this.
We'll have 73 then 183.
And then 384.
374.
65.
185 and 247.
So this is after performing counting sort on the unit digits.
Unit digits.
So you can see they are sorted.
So you have three three.
Then you have.
For.
And you have four over here, five over here, five over here and seven over here in in a similar manner.
Again after after this is over, let's just come back.
So after this is over we are again going to call counting sort.
And I is going to be equal to one.
Right.
So I is going to be equal to one at that time.
And then again we'll come inside and we will do the sort for the tens digits.
And after that I is going to be equal to two.
And we will do the sort for the hundredths digits.
And this is how radix sort functions.
All right.
So we have got a good understanding of this.
Now let's take a quick look at the time and space complexity of this solution.
Now the time complexity of this solution is of the order of d into n plus k.
And the space complexity is of the order of n plus k.
All right.
So over here K is the range.
So that's 029 right.
So 0 to 9.
Because this is in decimal system we can say this is just ten.
So let me just change this.
So because this is in decimal system we can say over here we can have ten.
And over here also we can have ten.
And over here D is going to be the maximum number of digits.
All right.
And n is the number of items or number of integers in the array which is given to us.
Now let's try to understand the counting sort will do n plus ten or the operations of the order of n
plus ten or n plus k every time it is called.
And we will call this d number of times, which is done over here in this call, right in this for loop.
That's why the time complexity is going to be of the order of d into n plus k, or because this is the
decimal system D into n plus ten.
And the space complexity is of the order of n plus ten, because every time the counting sort is called,
we will use up space of the order of n plus k or n plus ten.
And again it's it's not going to be d into this because we don't need it.
After one call is over we can just use we can just leave that space or give it up.
So that's why the space complexity of the radix sort and the counting sort is the same, which is of
the order of n plus ten itself.
Now what are the things that take up space?
Let's take a quick look over here.
You can see we have the output array.
So this takes up space of the order of n.
We have this temp array which takes up space of the order of k.
And in this case k is equal to ten.
And we have um is there anything else.
Let's just see.
Is there anything else that takes up space.
No there is nothing else.
So these are the things that take up space.
So we can say that the space complexity is of the order of n plus k.
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.
All right.
Now over here also we can say time complexity is of the order of D into n, because over here k is a
constant which is ten.
Now let's also take a look at the things that take up uh time.
So again we have seen that over here.
We are doing it d times.
So we have a D over here.
And the counting sort is of the order of n plus k.
So let's see what are the things that take up space or take up time in the uh counting sort.
So let's take a look at that.
So we have the counting sort function over here.
Now we are.
We are going to take up time when we determine the frequencies, right?
For example, over here.
This is going to take up N operations.
Right.
So we are looping through the array and there are n elements over here.
So this is going to be n operation here.
Also we are going to have n operations right.
Because we have to loop through the output array and fill it with zero.
And over here also we are going to have k operations because that's going to be the length of the temp
array.
Right.
And then we are looping through the temporary and filling with zero.
And again we have seen over here we have N operations.
And then over here you can see we are looping through the temp array.
And we are finding the cumulative sum.
So this is going to be again k operations.
Right.
And over here we are looping again through the array right to fill the output um array with the correct
elements.
So this is again going to be another n operations.
And inside this the operations are just constant time operations.
That's why you can see there are total of n three times n and two times k.
So we could say three n plus two k.
But that's just n plus k because we are avoiding the constants.
So that's why the time complexity of the counting sort is n plus k.
And we are calling it d times.
So hence we can say the time complexity of this solution is of the order of d into n plus k or d into
n plus ten.
Because over here we are dealing with decimal system.
And we could say we can simplify this further.
We could say the time complexity is of the order of d into n, because this is also a constant in this
case.
And the space complexity is of the order of n.