Hello everyone, in this lesson of the Data Structures and Algorithms courses, we continue to learn Chapter 8, internal sorting.
Since binsort can only deal with situations of small m,
what about the case with a large m, even larger than n?
Then we can imagine that, if we are able to
split the key values of these records into several parts,
then we can finish this sorting after using binsort several times.
Actually, radix sort is based on this thought. Now, let us firstly look at the radix sort.
Here is its definition. For this key value K, we artificially split it into such child key values.
This Kd-1 is its highest bit. What about K0?
It is the lowest bit. What about the case that the sequence can be ordered on such a set of key values?
That is to say, for any two records Ri and Rj,
if i is smaller than j,
its corresponding group and key value are smaller than those of the other one.
We can see that , for this, the situation of a combination of key values,
in fact, the maximal radix comes first. If we can find out which is larger only according to the highest bit,
then we can be sure which actually is larger. If they are equal until the last bit,
Then the key values of the two records are equal to each other.
Of course, the same key values are not able to demonstrate that these two records are also the same.
It is possible that we have repeated key values. However,
other information of the records can be different. For example, if our key values are the person's name,
for two persons with the same name, they are probably two different individuals. There is other information to distinguish these two persons.
In radix sort, we can see how we artificially split out such
long or a relatively large range of m as key values.
If the data ranges from 0 to 9999,
then we can follow one, ten, one hundred and one thousand to split them.
Of course, if we are split from the highest bit to the lowest bit, it becomes one thousand, one hundred, ten and one.
In this case, we change it to a basic question which only needs to sort four times.
If we are able to make sure which is larger only according to the highest bit, of course, we finish the comparison, right?
If they need to be compared on the second highest bit, we split them successively.
So that is what is called radix sort. In fact, here we
regard 10 as its radix. Then,
we split them with radix 10, and the value is split into 4 parts.
Now we look at some other cases appropriate for radix sort.
A typical example is sorting for poker cards. We assume that,
we firstly order them according to their variety, and for the same kind of variety,
we compare their numbers, which means, the number on the card.
Now we sort for such a set of data.
Firstly, if we order them according to the highest bit, we can use the methods of recursion and division.
If we want an ordered sequence from the minimum to maximum,
it is club on the top,
then diamond, heart and spade.
After split them according to their variety, for each bin with a particular variety,
it just needs to keep its own part.
Now it has an order if only based on variety, and then we continue to sort according to their numbers.
In fact, it is a process of divide and conquer recursion.
Firstly, we order them according to their lower bit.
In this case, we need to notice that, we'd better to choose a stable sorting algorithm.
Then, for the numbers, we get such a sequence. Now we can see that,
There are 2 cards with a number 3.
Then we order them based on the variety, now only considering the variety, not caring about the numbers.
For this case, we can see that, club 1 and club 8 are both clubs.
We can see it is the second time that club 8 appears, so according to our convention, we mark it with a single quote.
If we can guarantee its stability,
club 1 should be already in front of club 8 according to their numbers.
If its stability can be guaranteed when we order them based on their variety,
Club 1 must come before club 8.
This makes our overall sort an order one.
Actually, one point is that, when we sort the first time,
it is not necessarily a stable one.
Yet the sorting must be guaranteed to be stable from the second time.
Now we look at the several methods that we just said.
In fact, we analyse it separately, and we can see it is just such a process.
Put them into several bins orderly according to the highest bit, further divide each bin into smaller bins,
until its lowest key value.
So this process actually is splitting, splitting, splitting, splitting and collecting.
Yet the collecting doesn't seem so obvious. If we have the ordered bins,
and each bin has been sorted separately,
then the last collecting is a very obvious process.
Then we look at the method with a priority of low bit, it starts the sorting process from the lowest bit.
Then, after sorting, we continue to sort based on its second lowest bit, and we do this until the highest bit.
Our sorting process, in fact, split first before sorting,
which means divide them into different bins, and then collect them together.
Before finally finishing sorting, it is a process of splitting and collecting for many times.
For the method with a priority of low bit, it seems not easy for us to understand, or we say that it looks very awkward.
For the method with a priority of high bit, we can deal with it conveniently due to its idea from the top to the bottom.
However, for the method with a priority of low bit, it is very efficient when a computer calculates them.
This lesson introduces some related algorithms with a priority of low bit.
Now we look at the specific implementation of radix sort.
We discuss two kind of algorithms, sequential one and chain structure.
Now we look at the sequential method. In fact,
We just repeated using binsort. For example, we have such a set of data.
Firstly, we sort for the bit of units.
This process is the same with binsort, yet the first time, we only care about the bit of units.
We split them based on its bit of units, firstly a radix,
And then we put them to the corresponding bins.
Then we collect them, which means
to assign them into the most appropriate bin, yet now we don't look at their bit of decades.
We only care about their bit of units and make them ordered, 1,2,3,6,7,8,9.
With this result, we continue to make such a binsort.
This time, we look at bit of decades instead of units.
Well, similar to the previous assignment, with this result,
we only care about bit of decades, not look at bit of units.
However, we should note that since our second time of sorting,
it is necessarily to choose a stable algorithm,
due to the fact that we should keep
the relative order given by the bit of units.
finally we get a proper sorting result, and this result is stable.
Now we look at a kind of radix sort implementation based on array.
It starts with some initialization work.
We need to pay special attention that we should retain a variable to deal with radix.
We use it to get the value of the ith bit.
Firstly, we assign according to the ith key value,
and when we do this,
we count for the records in each bin.
we can just get the i-th key value at the present.
What we should do here is,
for the element to be sorted,
We divide it by the Radix. In fact, we remove some bits of its right side.
Then, for the radix r,
we do a modulo operation, which aims to
remove some relatively high bits from its left side, and just get the i-th bit.
Then we get this value k, and for the corresponding bin, we add its count by one.
We calculate the range of index for the bin, which in fact, is that
we need to find out for the i-th bit,
what the sum of counts of bins in front of the bin with an index j is, and again add the count of itself.
We will use this value when we assign later.
Then we go on the assignment.
We collect from the end of this array, which means from right to left.
When we do this, it is similar to what we just did.
We get the value k first, which is the value of the i-th bit of the present value.
Then we check the count of the corresponding bin.
Then, due to the fact that we record the cumulative values before,
the value should be minus one, to get
its proper index in this result array. After getting this index,
we put the element to be sorted at the present
on the proper position with a corresponding index in the array. After sorting,
Finally, we should remember to copy the content
back to the Array. In other words, in our sorting process,
for the Array and TempArray, data are often copied to each other.
This makes our whole sorting process more convenient.
Then we have to remember after this round of sorting, we should multiply the Radix by r,
which means, now we change over to one bit ahead.
For example, if r is 10, then for the first time, our Radix is 1,
which means we get the value on the bit of units. For the second round, Radix is multiplied by 10 so it equals to 10, which means to get the value on the bit of decades.
Then the next time, multiplied by 10 again and it becomes 100, on the bit of hundreds. That is the role it plays.
Now we analyse the cost of time and space of radix sort.
Firstly, for its space,
they need such a large temporary array, that TempArray which we've seen before.
It is able to store all the data to be sorted.
So it is Θ(n). Besides, we need
r bins. We mainly use them as
counters, and in fact, the bins
are in that TempArray. We figure out its logical
interval of data, and this interval is stored in the counter.
Then we put the data inside it,
so we do not really open up space for a bin.
Therefore the total cost of space is Θ(n+r).
For its cost of time, in fact, for one round of binsort,
it is obvious to scan these corresponding i-th bit of the data, right?
Then, for the array of counts, do the corresponding operations.
So as for its cost of time, it is Θ(n+r) for one round.
In the process of radix sort, we artificially divide it into d fields of data,
and combine to a composite type of key values.
So what we have to do is doing this binsort for d times.
Its cost of time is d*(n+r).
Now we look at this algorithm again. We consider that,
it seems like our binsort before.
It also seems there are some difference, which is to say, after counting, it only needs
to output the corresponding value directly according to the situation of this count.
However, we think about, what it really has sorted?
It seems that it just output these values.
If these elements to be sorted include other information besides key values,
Is it able to complete binsort with such a framework?
Actually it seems not. Thank you.