Hello everyone, in this lesson of the Data Structures and Algorithms courses,
we continue to learn Chapter 8, internal sorting. Today, I will introduce index sort.
The result of radix sort which I introduce before,
it puts the order of this sorting in the fields of next.
For its values, they keep their original appearance.
If we hope to arrange these values to an ordered result
according to the indexes after sorting, then we need an algorithm to do this arrangement.
Now we start with making such a pointer j
point to the smallest element in the result.
We deal with them successively, to get the i-th element.
We firstly store the i-th element
of the present result in this temporary variable Temp.
Then, we swap the element that occupies the i-th index
and the element that should really be
on the position of the i-th index.
Meanwhile, we should note to modify
the i-th element which has been on its appropriate position,
and its filed of next
points to that pointer j when it came here,
which means we keep the trace of swap.
Then, we need to deal with this j-th element.
Again we go along the field of next of this TempRec we just kept,
and we turn to such a next element to be dealt with.
If this j we've got is smaller than or equal to i, it indicates that
this j in fact is a trace.
We have to go alone this linked list, to find
a position of j which needs to be dealt with.
Then we repeat this process all through, and we can finally arrange this linked list in Θ(n) time.
The result is ordered from small to large according to our indexes.
If we find that the field of data is vary large,
since the cost of time of your sorting algorithm mainly consist of comparisons of two records
and the moves of records,
for this situation of large field of data, if there are many moves on bits, it will cost lots of time.
Then are we able to construct an index?
We find that when the record needs to be swapped or assigned a value,
We only do the operation to the index instead of arranging the data field.
Our sorting result is stored in such an index array.
Finally we arrange the data field only once according to this index array.
Then we are able to save the time of sorting.
Now let us have a look at such a representation before,
for this set of records,
we put the result into such an index array.
If we can open up a new array,
then we are able to know, for example, the data on the position with an index 5
should be put on the position with an index 0, so we take it directly from this side,
and then we deal with this successively.
We also finish the arrangement in Θ(n) time, yet with a relatively expensive cost of space.
In fact, we don't need to open up a new space, and I will introduce a method of arrangement later.
Now we've learnt such a method of index sort, which in fact,
is appropriate for the internal sorting methods we've learnt before.
What we need to do is only changing operations of assigning a value and swapping
to operations on our index array. Of course when we compare
the key values of these records, we also have to compare
the corresponding element that the index field points to.
Now we have a look at insertion sort, how do we modify it,
in order to make it an index sort. Firstly, we make
this index array, its index field,
points to itself, which means it is on the position that it should be on.
Then we see, following is a classical framework of insertion sort.
When we want to deal with the i-th record,
and the 0-th to i-1-th records before it are already in order.
we need to insert the i-th record to its proper position.
For this so-called proper position, we need to compare this i-th record
with the records in order successively.
We swap them if we find that they are in reverse order, until some record
and this i-th record that we are dealing with at present are in order.
Then, of course, they are in reverse order at the beginning, and when we find a pair in order, we stop.
Now we note that here of course our swap is for
the corresponding element in the index field,
which means for our index, instead of the data in the data field itself .
Then when we compare, it is also the corresponding key value of the data
which the subscript of the index points to
After our comparison,
we can get
a proper sorting result of this insertion sort.
Yet the result, is stored inside this index field.
We need an arrangement along its chain. Now we look at the process of arrangement.
If we don't open up a large array, how can we arrange it along its chain.
Firstly, we should put the value on the position with an index 5 to the position with an index 0.
We store the record on the position with an index 0,
and then we put the record with this index 5 on.
The value on the position of index 4 should be put onto the position with an index 5.
Now we move this 34' on and also the corresponding 34.
We say the value of index 0 should be put on the position with an index 2.
So we move this 29 whose index is 0.
Since we've stored it, what we need to do is just fetching it.
Now, a child loop has been completed. For
the result, they have been on their proper positions.
Then we continue to look at the element which hasn't been dealt with.
For this 25,
it is on its appropriate position. We go on
to the position with an index 3. There is another round of loop
to move it to its appropriate position.
Now let us look at the algorithm of this arrangement.
Firstly, according to the indexes from 0 to n-1,
we go along and do a single loop of process.
There are some smaller loops inside.
For the index of our present
i-th element, we store it in j,
And we store its value in such a temporary variable.
If the index that our index field points to
isn't equal to i, then we move the corresponding value
that we need to put onto the present carry bit
forward, and we should note that
we need to modify its index of index field correspondingly.
So the time when
our such a small loop is completed, it is just the time when
we see we return back the index field which is our starting index at the beginning.
So this round of the small loop has been completed. After this,
for the temporary record we stored before,
we fill it into this,
the record we deal with at last.
Meanwhile, we have to modify these index fields correspondingly.
When our loop goes on next time, if the record is on its appropriate position,
its corresponding index field, the index value is itself.
So we don't need to deal with this case, and our loops don't go on repeatedly and repeatedly.
We scan for one round, not care about those have been dealt with, deal with the latter ones.
We also have another method of index.
For this method, we can see that in such an index field,
it indicates which index position that the element itself should be on. For example,
The element 29 should be on the position of index 2. If we open up another array,
we are also able to scan for one round and fill it with these proper elements,
but it wastes space relatively.
Then we, similar to the first method,
don't need to open up another large array.
We use these fields of index to do the arrangement.
We find that at the beginning,
for the element 29, it should be on the position of index 2.
So, we put the value of index 2 into the temporary variable and move 29 on.
Then, for the position of index 2, it says, it should be on the position of index 4, so we thrust forward.
There is a small loop, until
we return back to the position where we start.
For this data, there are 3 rounds of this small loop.
Then we deal with these data successively, and finish the assignment.
Finally, let us think about some questions.
Firstly, we need to demonstrate that
they can be completed in Θ(n) time, for the arrangement algorithms of index sort that I introduce before.
And, as we've known, the first method of index,
is appropriate for those internal sorting algorithms we've learnt before.
We only need to do a little modification for it. Now we try to modify quicksort.
In our sorting process, we do the operations on
index fields instead of data fields.
After sorting, we have a process of Θ(n) time to arrange the indexes, and then
get an array ordered according to your indexes back.
Besides, we can search a method of Rank sort.
Through this method, we are able to get such an array in our second index algorithm.
Another thing is that for radix sort based on static linked list we've learnt last time,
we can make a simple change on its result,
and then it becomes our second index algorithm.
Thank you.