Hello everyone, in this lesson of the Data Structures and Algorithms courses, we continue to learn Chapter 8, internal sorting.
Our main content today is assignment sort, including binsort and radix sort.
In assignment sort,
There is no need to compare two records,
yet according to their key values.
So we need to know specific details of the record sequence, especially the distribution of key values.
We first introduce one kind of binsort.
If we know that all the records in the sequence
are located in a relatively small range of the interval,
then we can assign the records with the same key value to a bin,
And then we turn to collect these bins successively to get an ordered sequence.
Now we turn to an example.
For example, we have these records.
We can observe that these key values are in the range of 0 to 9.
So, we set up 10 bins, for each bin,
we can estimate how many records it will probably have.
Then we assign the corresponding records into each bin. However,
If the bin needs a piece of space which should be assigned physically, then it will get some trouble.
We'd better to use the position of the entire array.
Actually, the bins are virtual.
We do have a reserved position for each bin, and then we put the corresponding records into the bins.
We will get an ordered sequence after collecting them. Then we need to have a look,
Besides counting the records in each bin,
We look at the total amount of records in our previous bins.
So what we have to count is such a cumulative number.
For the bin with an index of 0, there is no record in it.
Then, we have two records after adding the records in the bin with an index of 1,
and then 3 records in total which begin with 0 or 1 or 2.
Accumulating like this, we get such a count for bins.
Based on this count, we can sort the records.
In this sorting process, I scan the records that need to be sorted,
from right to left.
That because for each bin,
we have got its cumulative count. For example, when we see the value 2,
We know that its cumulative count is 3.
It is to say that, in the whole array sorted already, there are 3 records in front of it.
So the value two, should rank the third place of the whole array,
which means, the position with an index 2. Then we subtract 1 from the count 3 that we just got, and get this index.
Meanwhile, we should also do a cut on this count, and then retain it
inside the bin of cumulative counts.
Now we look at this 1', the reason why we call it 1'
is that there is a 1 previously so this is the second time it appears.
Now checking the list,
we can get the position 2.
That means there are 2 records in front of it in the bin with an index of 1.
Therefore we put this 1' on the second position of the array,
which means, the position with an index 1, and the count should be also minus 1.
Now looking at this 8, it is also 8'. Then we check the list again.
There are 8 records in front of it cumulatively,
so it should be put on the position with an index 7.
Then we also do a cut on the count.
Now looking at this 1,
it must rank before 1', since we regard it as the last one,
among all the elements that related to the bin marked 1.
When we see 1, we check the cumulative count.
Then we get such a count,
with an index before 1, which means 0.
So we keep its stability.
For other elements, we also follow this process successively.
Finally, it becomes an ordered sequence, and it is stable.
For the binsort algorithms, we've done some initialization work.
Then, from the position with an index of 0 to the position with an index of n-1, we
scan the key values of a record successively.
Then, put them to the corresponding bins.
The count of this corresponding bin will increase, so this is an algorithm with a complexity of Θ(n).
Then we continue to deal with this array of count.
We sum all the counts of elements in bins before,
as the present value of the array of counts, which means,
we get the count of elements less than or equal to i.
According to our sorting process, we know that
We deal with the array from the right side, which means n-1, to the left side, which means 0.
When we get an element,
we check the corresponding array of counts,
and then we get the value before a subtraction,
and then for the element we are dealing with now,
We put it on this corresponding position. After this whole process,
we get an ordered array, and it is stable.
We look at some performance of this binsort algorithm.
Firstly, we mainly consider several aspects to analyse its cost of time.
For the counts, we must scan each element,
so it is Θ(n).
Besides, for the array of counts,
we sum all the counts of elements in bins before,
Therefore, it is Θ(m).
We sum the time spending on checking the amount of elements and counting for bins.
Then we get an cumulative time of Θ(n+m).
For such a binsort,
Obviously we can see this cost of time,
Generally speaking we know that it fits the situation that m is much smaller than n.
Otherwise, if we have an m which is larger than n,
or its range is very very large, then we need a lot of bins.
This is less cost-effective. For the complexity of space, the most important cost is that
we have m counters to record the amount of elements in bins
and the cumulative amount of elements in bins before.
Besides, we also
need to open up a temporary array of length n, mainly for
putting the data in this binsort to this temporary array from an array which needs to be sorted.
Then we use that array to be sorted to get the results,
We turn the corresponding elements in the temporary array back.
So we also have a cost of Θ(n+m).
We just saw its algorithmic process is stable.
Again we have a few questions to think about. Firstly, if we want to use binsort,
How large should this m be to be an appropriate value? How we should deal with if it is too large?
What is the array of counts used to do in this binsort?
Besides, why we collect the data from the end to the beginning?
Actually, we've answered these questions before. Thank you.