- [Instructor] Bucket Sort and Radix Sort.
Bucket sort and radix sort
work by distributing and collecting
the elements to be sorted.
They don't perform comparisons.
This is a different approach
from any that we've seen so far.
All the algorithms we've seen so far
use comparison to perform the sort
and these algorithms can't do any better
than big O of n log n.
But bucket sort and radix sort don't perform comparisons.
They're sorting algorithms that work best when
we have more or less uniformly distributed data.
And we'll see that bucket sort works best
when we have a limited range of possible values.
Here's pseudocode for bucket sort
adapted from the textbook.
We take an input vector.
We make some buckets
to places where we're going to hold elements.
We distribute the elements into the buckets
then we sort the items within each bucket.
And then ,we gather the results back
into the original vector.
Needless to say, this pseudocode here
sweeps a lot of detail under the rug.
Let's look at this in a little more detail.
This again is adapted from the textbook
figure six dash 12.
We start with an unsorted vector of values.
Notice that we have 10 values
and their range is relatively restricted.
All of these values fall within the range zero to 100.
We don't have 10 million, for example.
First we distribute the elements
into the appropriate buckets.
This first bucket here, holds values from zero to 19.
The second holds values from 20 to 39.
The third holds values from 40 to 59,
the fourth 60 to 79
and last 80 to 99.
Then once we have all the values
in their respective buckets,
we sort the values within the buckets.
And from there, it's a simple matter to gather the results
and return them to the original vector
now in sorted order.
And again, there's a lot of detail
being swept under the rug here.
For example, how do we decide how many buckets to use
and how do we sort the elements
once they've been distributed into the buckets?
Let's set aside for the time being
the question of how many buckets to use
and focus on this second question.
The answer is any number of ways.
We could recursively call bucket sort on each bucket
as we've seen with the divide and conquer approach
or we could use another sort algorithm
like insertion sort to sort the elements within each bucket.
And there are times when you'd like to implement
bucket sort in different ways
and different sorting algorithms might be appropriate
at this level.
Now to the question of how many buckets to use.
Obviously we don't want just one, that would be no help.
We take the whole input vector,
dump it into a single bucket and nothing would be changed.
And we don't want the same number
of buckets as there are elements in the vector
that too would be no help.
So the answer is, again, it depends
and there's no hard and fast rule.
It depends on the nature and distribution of your data.
What do I mean by that?
Let's look at some examples.
Here we have a vector 3,000, 1,000 zero and 2,000
and we wanna sort this using bucket sort
but notice that the values are pretty well spread out.
They range from 3000 to zero.
They are only four values.
So that's kind of sparse.
We'd call that sparse.
And if your data are sparse
you don't wanna have too many buckets.
Let's say we had this vector as data.
And if we want to sort these
it wouldn't do as much good to have 600 buckets.
We'd wanna have something say
between three and five buckets.
Now look at this vector.
This is very different.
What if we had data like this,
densely clustered around a single value.
Notice that all the values are pretty close to 2000.
There's a big gap from zero to 1998.
There's nothing beyond 2010
and everything is closely clustered around that value 2000.
So what happens if we have data like this?
If we make our buckets too big
then all these values might wind up in the same bucket.
And as you might expect, worst case performance
for bucket sort occurs when all the values
fall into a single bucket.
Which brings us to the question
of Bucket Sort Complexity.
Assuming data are reasonably uniformly distributed,
assuming that they are, and that you have n elements
and m buckets,
distributing takes n steps
because we have n elements
we have to dish them out into so many buckets.
Sorting each bucket takes f of n divided by n steps
where f is the runtime
of the function used to sort the buckets.
So you recall, I said
we could use a bucket sort recursively
or we could use insertion sort.
This step depends on the sorting algorithm that we choose.
But with m buckets, we multiply and we get
m times f of n divided by n
and gathering takes n steps.
We have n elements, it takes n steps to gather them.
So we wind up with big O of n
plus big O of m times f of n divided by n
plus O of n
and
this,
n divided by n, that's just the number
of elements divided by the number of buckets.
That's a constant.
And we have two O of n terms that gets us O of two n
and we just ignore the leading coefficient.
And so this whole thing simplifies to big O of n plus n.
And notice that this means
that performance depends on the number of buckets.
Also remember that this only holds true
if the assumption we gave before is true,
that data are reasonably uniformly distributed.
Now let's add bucket sort to our comparison chart.
Here we have bucket sort.
We see that it has big O of n plus m time complexity
big O of n plus m space complexity.
And it depends, whether it's stable or not.
What does it depend on?
It depends on the sorting algorithm
that's used to sort the elements within each bucket.
If we choose a stable sorting algorithm
then bucket sort will be stable.
If we choose an unstable sorting algorithm
than bucket sort will not be stable.
And this note is important
bucket sort requires that certain properties
hold for the data in order to be effective.
Now, let's look at a cousin of bucket sort
called radix sort.
Radix sort is a related algorithm that works with data
that could be sorted lexicographically.
What does that mean?
Lexicographically?
Well, lexicographic sorting is just like
sorting words in a dictionary.
In a dictionary,
we sort on the first letter
and then on the second letter and so on.
So aardvark comes before Abacus.
That's what we mean by lexicographic sorting,
it's dictionary sorting.
And here we'll take a look at sorting numbers
based on their digits
but we're going to work from the least significant digit
to the most significant digit.
This is called LSD radix sort.
And radix is just another word for base
as in base two for binary
or base 10 in our everyday counting system.
The radix is the number of digits
that we have in our system.
So for base 10, we have zero through nine
and radix sort complexity is big O of n times d
where d is the maximum number of digits
among all the numbers we wish to sort.
So radix sort can outperform big O of n log n algorithms
whenever d, the number of digits is less than log n.
Now it may surprise you, but radix sort is old.
Here's a tabulating machine
that was used to sort punched cards
in the 1890 census using the radix sorting algorithm.
And while it's been around a long time
it wasn't until the mid 1950s
that an efficient implementation
was invented to run on a computer.
So we've known about radix sort for quite some time
but it's only been within the last 50 or 60 years
that we've been able to run it effectively on computers.
Here's pseudocode for radix sort
and note that this is for lexicographic sorting
of integers by digit.
We take an input vector,
we're working in base 10, so we make 10 buckets.
And then for each digit
let's say our largest number is 4,212
we have four digits, for each digit for each element
we distribute into the appropriate bucket
based on the digit.
And then for each bucket
we gather the results back into the original vector.
And we repeat that for each digit.
Let's see what that means.
Let's say we have this vector
one nine two three seven nine and so on,
notice that I've inserted a leading zero here
two leading zeros here,
leading zero here
to show that
when we sort on this digit
that this value is zero.
And when we sort on this digit, this value is zero.
So for our first sort, remember that we're working
from least significant digit to most significant digit.
We're gonna sort on these digits in red
two, nine, two, seven, four, five, four, three.
And if we do that, then we get this result.
This is our resulting vector.
Notice that the twos begin for us
then the threes, the fours, the fives, seven and nine.
Then the next sort, we're going to sort
by the second digit
nine, one, zero, zero and so on.
And if we do that, we'll get this resulting vector,
notice now that the zeros are leading,
followed by the ones, a five, two sevens and a nine.
Finally, since we have three digits
we sort on that third digit
and now see we have
two, zero, zero, zero, four, two, three, one.
And if we sort on that third digit
we get this result
zero, zero, zero, one, two, two, three, four.
And now you'll notice
that our vector is in sorted order.
So we sorted our vector without performing any comparisons.
Now, how do we get the value of a digit
without performing comparisons?
Well, we take the number
we divide by the appropriate power of our radix or base,
and then we take that value modular the radix.
So if we're working in base 10,
as we've been in these examples,
to get the third digit of 2,708
we integer divide by 10 to the two,
notice that we zero index the digits, which gives us 27.
And then we take 27 modular 10, which is our radix,
and that yields seven.
And so the third digit
of 2,708
is seven.
So we now know that on our third iteration
2,708 will get distributed to the sevens bucket.
Notice that the buckets are also zero indexed.
Let's take a look on visual algo.
Notice that we have input values from one to 9,680.
We create those 10 buckets
and they're using red
to indicate the digit that we're sorting on,
the least significant digit.
And then we dish them back out to the vector.
Then we do that again for the second digit
and notice that we take the elements out of the buckets
in the order that they went in.
Now we do it for the third digit
and dish them back out to the vector,
and then we'll make one more pass for the fourth digit,
and we'll be complete.
We skip the empty buckets. That's simple,
and now we're done.
Now we return to our comparison chart
and we've added radix sort.
We see that the time complexity is big O of n times d
where d is the number of digits that we have to work with.
And n is the number of elements in our vector.
Space complexity
is O of n plus d
radix sort is stable
but it also requires that the data
can be sorted lexicographically.
It won't work with any other kind of data.
So in summary, bucket sort and radix sort,
perform sorting without making comparisons.
They distribute and collect.
They can outperform big O of n log n algorithms,
but only under certain circumstances
the data have to have certain properties,
both in terms of the data type
and the distribution of the data.
In the next video, we'll implement a version
of radix sort in C plus plus.
That's all for now.