Hello everyone, in this lesson of the Data Structures and Algorithms courses,
we continue to learn Chapter 8, internal sorting.
We will look at an implementation based on static linked list.
If we store the child sequence assigned out
into such r static queues,
then for each of these queues,
it can be regarded as a bin, and it is a real queue for this.
So comparing to what we did before, which means we use arrays,
they are different since the space of bins is virtual.
Yet now we really open up the bins.
Here we should note that we use static linked list, which means
we use a relative index of array instead of a real
dynamic array of pointers, since if we use this,
it will lead to an expensive cost of space.
Now we look at a representation.
Firstly, do a binsort for the bit of units.
it is easy, and here we use ten bins, since our data has a decimal system.
Now we assign these data from left to right appropriately.
97 is put into the bin with a mark 7, and then we go on with 59 and 26. For each element,
since we should keep its stability,
it must be put at the end of the queue of bins.
which means we use queue to indicate the bins.
The element being put must be at the end of the queue.
Therefore, when we collect them, what we need to do is to make these queues end to end successively.
Then it becomes an ordered sequence based on the bit of units.
Yet we haven't finished the sorting process, since we don't deal with the bit of decades.
Now we continue our sorting result,
only care about the bit of decades instead of the bit of units. Then, we assign all the data
into its corresponding bin.
This result is the sorting result that we make these bins which are not empty
end to end successively.
This is the second round of sorting, which means the highest bit of the data.
Now we finish the sorting process, and we should notice that
the second round is based on the result of the first round,
so we have to choose a stable sorting algorithm. Now we look at
the definition of static queue, and
our structure based on static pointers.
We implement the radix sorting.
For convenience, we expand the elements to be sorted
with one variable, which indicates,
in the linked structure of elements,
which is next to me.
In fact, it becomes a structure of single link,
only using next to point to the next node.
and this next node, in fact, it is the value of the index.
We save the index of its next node in the pointing space of this next.
So it is a structure of static linked list.
For our queues, we need to keep its pointers of the start and the end.
Here, it is also
only a value of the index. Then we look at an implementation of radix sorting based on static linked list.
We also begin with some initialization work. Here we should especially pay attention.
Now we begin.
Originally, the data is in an array.
After we add this field of next, for data in the array,
we make them a chain by putting them one by one together, and then we can see
i+1 is next to me, which means
i+1 is next to i in this Array.
We construct the whole structure like this.
For the last element, -1 is next to it,
which means it is the last one in our queue,
with the same meaning of null in dynamic pointers.
Then we assign and collect for the i-th key value.
Since we split the whole key values into four parts,
here we need assign and collect for d times in total.
We will introduce the process of assignment and collecting later.
After we do this assignment and collecting d rounds,
then we get the result array, however, we should note that
in fact our sorting process
is based on static link list, so the array we get is fields of these pointers.
We put them one by one together, to indicate their corresponding order.
For our whole array, if you look at the index from 0 to 1 to 2,
look at the elements of the array, in fact, it
is not in order. It is in order through linking them together by the fields of next. We can look at an example later.
So we have to arrang them after sorting, which is that,
according to its index information in the field of next,
we arrange the data, put them to the array,
make them in order according to the index.
Meanwhile, for the field of next, actually we don't need to necessarily put it
together with the key values of the original array as a node.
We are able to establish a linked list which is particularly for the field of next.
That is an array parallel to the array. We should noted
the corresponding relation of these indexes. Of course it looks a little difficult for this implementation.
So here we put the key and next together to think about.
Now we look at the radix sort algorithm based on static linked list. Firstly,
Our this current,
We firstly make it represent the first element in the whole array to be sorted.
Then we make null as the value of each bin.
Then we go along with the data and their corresponding linked list of next
that this current point to.
We get these elements to be sorted successively.
Now firstly we get key value that
the present element points to.
Then we put it into k. And then we fetch the i-th bit,
its key value. The way we fetch the key value of the i-th bit,
is similar to that of using radix which we said before.
So here what we convey into, is the value we fetch from the present i-th bit. Therefore,
here we make it divided by the radix for i times,
which in fact means that we remove
some bits from the end.
Some bits here means i bits.
Remove them, and then do a modulo operation,
in order to remove its some bits from the left. So we justly fetch the i-th bit.
Then we put this value,
into the corresponding k-th bin.
If the j-th bin is empty. it will be the first element.
Otherwise, we put it to the end of the queue of the k-th bin.
And for the end of the queue of the k-th bin,
now the pointer points to the present current.
Then our this current, it points to the next bit of the element to be sorted in this array.
This is one round of assignment.
Now we look at the process of collecting.
In this collecting process, we in fact put these bins that aren't empty
end to end together successively. Then we will finish this process.
Firstly, we need to find out the first bin that isn't empty. After finding it, the head of the whole result,
points to the head of this first bin that isn't empty.
Now we make this last point to the end of the first bin that isn't empty.
Then we find the next bin that isn't empty, and we put it
just behind the previous bin,
its end. Then we make this last go along.
We should note that after we finally finish collecting, the final position of that last,
its field of next, must be -1, which means,
for the last element of a single linked list, its field of next should be null.
When we do some operations later, it can make sure
the search for this queue, when it see this null,
which is -1, it is able to stop. Now we have a look at
its cost of space and time.
Firstly, it has space for n records, which is also used to rotate these data.
Besides, it also has r bins, which is pointers that
indicate the head of queue here, so totally speaking,
its cost of space is Θ(n+r).
For its cost of time, it is similar to the radix sort using sequential framework, and we also divide it into d rounds.
For each round, we scan all the data to be sorted, so
its cost is n, and for
each of the r bins, we also need to scan.
we put it in when we assign, and then
when we collect, we also need to put them end to end together. Therefore,
its cost is Θd*(n+r).
We see that its cost seems
to be d*n. Yet d seems to be a relatively small value.
Then we can say our algorithm is an linear one,
which means Θ(n).
However, it isn't like that actually, since our d, we can say it is dependent on n.
We can imagine that, when there is no repeat key value,
we code these n different data.
We must need d bits, which is
the logarithm of n based on r, so d must larger than or equal to log n.
Such a value, we can say it is inside Ω(log n), so
the whole cost, we substitute into it,
is n multiplied by log n.
Now let us have a think, for the radix sort algorithm with sequential framework and linked list,
what are their advantages and disadvantages, and which do you prefer to?
One problem, for radix sort using linked list, its result after sorting,
in fact the key of your original input is like this,
and then, in this field of next, there are these corresponding values.
In fact, through this field of next,
it can point out
their relative order. For example,
the smallest element is on the position with an index 6, and,
its value is 13. Then,
the field of next of this index 6 is 7, which means the second smallest one is 27.
We check them one by one through these fields of next. We can get
an ordered sequence from small to large.
However, we can see,
the array itself, isn't changed.
If we hope the result to be returned is an array, according to these indexes, it is in order, which means,
the element 13 is just on the position
with an index 1 or even an index 0, dependent on your request.
Put it on this position, and then output.
Then what should we do to arrange it? I will introduce it in index sort next time.
Thank you.