- [Instructor] Hey there.
Let's do radix sort.
As you recall, radix sort works
by distributing and collecting.
It sorts without making comparisons.
We proceed digit by digit or letter by letter.
And distribute out to bins or buckets
and then collect the values into our vector
and we iterate as many times as we have digits or letters
that we need to work with.
And so each implementation of radix sort
is going to be a little different.
I would write a very different algorithm,
well, not a very different algorithm
but I would write a different algorithm
for working with strings
than I would for working with integers
and that's one of the reasons
why we won't implement this as a templated function,
like we've done with so many others here.
So let's begin.
I'm gonna create a file called radixSort.
And we're gonna need
vector obviously.
And we're gonna include cmath.
Cmath is the standard math library
and we're gonna use powers and logarithms.
You'll see where we do that
but that's for calculating the number of digits
and recovering a specific digit for a given number.
Include iostream
and let's get that snippet we've been using for printVector.
Okay.
And now let's get down with the business of radix sort.
So we're going to have a void function.
Call it radixSort.
That makes sense, right?
And it's gonna take a std::vector
and we're gonna make this implementation for integers,
specifically nonnegative integers.
And we'll call that v.
And we also need to pass in the number of digits.
Int numDigits
so that radixSort knows how many digits
it has to work with, okay?
Because we're gonna iterate over the number of digits.
And let's do this.
I showed you function overloading before
and so we're gonna create another void radixSort
that takes, I'm just gonna copy this, std::vector.
And just that.
And so that's gonna have to calculate numDigits
and then make a call to radixSort,
providing numDigits, so the last thing this is gonna do
is gonna call radixSort
with v and numDigits.
And that's gonna live there in red
until we get that resolved.
And then finally, we need main.
Int main.
And no parameters and return zero.
Okay.
So let's get started.
I'm gonna start with this one.
So the first thing that we're gonna wanna do
is we're gonna want to calculate the number of digits
and that's gonna add some overhead to our algorithm
but it's only gonna add one pass,
we have to make one pass through the vector
in order to find the largest number
and then from the largest number,
we'll calculate how many digits it has
and then call radixSort with that number of digits.
So scanning the vector to find the largest number is easy.
We start with int maxNum
and since we're working with nonnegative integers,
we'll start that at zero.
And for int,
we'll call that num in the vector, right?
And we know that's gonna be an integer
because we're working with a vector of integers,
not a vector of comparables.
If num is greater than maxNum,
then we update maxNum.
Okay, that's it.
So now we know what the largest number is in the vector.
And then we need to calculate how many digits it has.
So int numDigits
equals, and I'm gonna type this out here
and then explain it to you.
We're gonna use the standard log base 10 function
and we're gonna call that providing maxNum
as a parameter
and then we're gonna add one.
Okay, so what are we doing here?
We've got maxNum,
so we're calling log base 10 on maxNum
and so if maxNum is say one,
we take log 10 of one.
That gets us zero plus one gives us the number of digits.
If it were 10, we take log base 10 of maxNum
and we'd give us one
because log base 10 of 10 is one.
Add one to get the number of digits.
We have two digits and so on.
So this gives us the number of digits
and now we can call radixSort
with that number of digits
and so that's going to be this function here.
We're gonna start by creating a number of buckets
and again, we're working in base 10
and we know they're integers,
so std::vector,
std:vector, oops,
of integers.
We'll call that buckets.
And we're gonna have 10 of 'em, okay?
So all this is doing is creating a vector of vectors.
So it's creating a vector of our buckets.
Our buckets hold integers
and there're gonna be 10 of them.
One for the digit zero, one for the digit one,
one for the digit two, up to nine and so on.
And now we're gonna iterate through the digits, okay?
Remember, radixSort is gonna do what it does
for each digit.
So for, and I'm gonna call this iteration equals zero.
Iteration less than numDigits.
And ++iteration.
Okay?
So that's our outer loop.
And then what we're gonna do
is we're gonna copy the items
from the vector
into the appropriate buckets.
Okay?
And we do that with another for loop.
For int i equals zero,
i less than the size of the vector.
++i.
And then in the body of our for loop,
we have to calculate the digit,
so int digit
and here we're gonna make use of the math library again.
V sub i divided by int std::power 10, iteration.
And we're going to take the modulus 10.
So that's a lot to grasp at a stroke.
But if you'll think back,
I did present this formula in the earlier video
and what we're doing is this std::power
is just exponentiation.
It's taking 10 and raising it to the iteration power.
So on the first iteration, iteration is zero.
10 to the zero is one.
This becomes one.
On the second iteration, iteration is one.
So 10 to the one is 10.
This becomes 10.
On the second pass, or the third pass I should say,
this value's gonna be two,
this is gonna return 100 and so on.
And then we divide v sub i by that amount
and then we take the modulus base 10.
So let's say we had the value 2,712
and we were in the third iteration.
On the third iteration, iteration will be two power of 10
raised to the two is gonna be 100.
We're gonna treat that as an integer.
We're gonna divide v sub i,
which I just said is this hypothetical number, 2,712 by 100.
That's gonna give us 27.12.
And then we're gonna take the modulus base 10
and that's gonna give us seven.
So the digit then, the third digit
of 2,712 is seven, and that's what this code does here.
So now we use that digit value
as an index into buckets.
So buckets, digit,
push_back v sub i.
So we're gonna push that value
into the appropriate bucket.
And that is our first loop.
And now what we're gonna do
is we're going to copy everything
from the buckets.
Ah.
Back into the vector
in appropriate order.
Okay, so here's how we do that.
We start by initializing a value.
Call it int i equals zero, okay?
And then for
int bucket
equals zero, that's an index into the buckets.
Bucket less than buckets.size.
++bucket.
So here, we're iterating through the buckets.
And then for each bucket,
we're gonna iterate through the items in the bucket
and then distribute them back out to
or collect them into our vector.
So for int item
equal zero,
item less than buckets,
bucket.size,
so we're gonna iterate through the bucket
and that's, sorry, ++item.
So for each bucket,
we're gonna iterate through the items in that bucket
and we're gonna collect them into our vector.
So v sub i equals buckets
bucket
item.
Right, so remember, bucket is an index into buckets
and item is an index into the individual buckets, okay?
Then what we need to do is to clear our buckets.
So buckets
bucket clear.
And clear is just a function, a method
that empties out a vector.
So we have this vector of buckets
and for this bucket, now that we're done with it,
we're just gonna empty it out.
So we empty it out.
And then lastly, we'll printVector.
V.
So we can see what's going on.
So we're going to watch what happens here.
And this is wrong.
Now, see, I've made a mistake here.
This is what I get for talking while I type.
This all belongs
in here.
Okay?
Sorry, about that.
My bad.
For each iteration on the number of digits,
we're going to copy items
from the vector into the appropriate buckets
and then copy everything
from the buckets back into the vector
in the appropriate order.
So sorry, I got a little ahead of myself typing that way.
So that should be radixSort.
Okay, so now let's test it.
We'll flesh out main here.
Let's see, we're gonna need a vector
of ints.
Call it v.
And we'll give it some values with various digits.
17, so some two-digit numbers,
some three-digit numbers and so on.
A one-digit number.
Oops, I left out a comma, sorry.
I'm doing a terrible job typing this time.
44, 115,
289,
28,
815,
71, 9, 84.
That should be enough.
And now we're gonna printVector.
And then we're gonna call radixSort
on v and that's gonna print automatically
but what it's gonna do first
is it's gonna call this radixSort,
which just takes a vector.
It's gonna calculate the largest,
it's gonna find the largest number,
then it's gonna calculate the number
of digits and call radixSort with the number of digits
and that's when we get to this radixSort.
So let's run it and test it.
And there we go, okay?
So this is our input vector,
which matches what we have here.
This is after the first sorting.
Remember, we have three digits.
So we're gonna have three sortings.
And notice here that we have a zero
in the first digit position,
ones followed by twos, three,
four, four, five, five, seven, eight, nine.
And now here,
on our second pass through the digits,
the second digit here is a zero.
This is a zero.
This is a one, one, one, one, two, two, three and so on.
And then here's the result of our final pass
where this three is implicitly preceded
by two zeros, two zeros, one zero and so on.
Up to 901 and we get a sorted vector out.
I think that's pretty cool.
I really like radixSort.
But anyhow, here's the code.
I'll post it on Blackboard.
And we'll see you later.