Because we only use a temporary variable when we swap elements.
Hello, everyone!
In this lesson, let’s continue to learn Chapter 8 —- internal sorting.
Today we introduce insertion sorting and variant of it —- shell sorting.
We can use an example of collating cards to show how the insertion sorting works.
If there are some cards which are already collated.
How do we insert the new card into the corresponding position.
Let’s look at an example.
If there are two elements,we can compare them.
If they are in reversed order, we can exchange them. If there are ordered, we can just leave them here.
compare 78 to the subsequence before it, it is in the right position.
When we want to insert 12 into the subsequence. we will compare it to the numbers before it one by one until we find the it’s right position.
we will do the same thing to the rest elements. Every element find the appropriate position
within the subsequence before it, and stay at there.
Finally, all elements are handled and we just finish the process of the sorting.
Let’s look at the frame of the insertion sorting.
Firstly, we store the element which is waiting for sorting in the temporary variable.
Secondly, we search the position from the position of it to the beginning.
Once we find a position that the element before it
is smaller than the element we are sorting, and the element after it is bigger then the element we are sorting.
And this is the position we want is to stay at.
After we find the right position, we just put the element stored in the temporary variable back to the right position.
In the loop, all the elements are handled in the order of positions of elements.
And then we finish the process of the sorting.
Let’s evaluate the inserting sorting algorithm.
At first, it is stable, because each element have compared all the elements
when it is inserted within the process of sorting. It never skip any element.
As for the cost of memory, the algorithm only use a temporary variable.
So the cost is theta(1)
And in the best case, the cost of time can be theta(n),
which means the original sequence is ordered.
And we just compare each element to previous one and find the right position. And we just compare n times.
Actually, there is a frame different from the previous one.It doesn’t have requirements of remove.
But in the previous algorithm, we just store the element waiting for sorting in a temporary variable whatever it is.
And put it back when we find the right position.
So even in the best case, It need not compare more, but we have already put it on the temporary variable.
And the right position is the position at where it originally stay.So we need to put it back to original position. hence there are n times of move we need.
In the worst cases, the original sequence is a inverted sequence.
For each element, we have to compare elements until we meet the first element.
Therefore, the cost of time is O(n^2)
What about times of move? Each element have to move to the front.
In addition, we need 2 auxiliary move for each element.，
As we put the element on the temporary variable and put it back at last. So the cost is sum of i+2 which i is from 1 to n-1.
And final result is theta(n^2) In the average cases, it still be theta(n^2)
The inserting sorting have two great property.
The first one is that it have low cost of time and is effective for mostly ordered sequence.
Just like in the case of positive sequence, it has the best cost of time.
It is also effective in the short sequence.
Shell sorting make use of these two property.
Let’s look at the concept of Shell sorting.
At first, we dividi the whole sequence into several small sequence.
then we use the inserting sorting in the small sequence, it is effective in this case.
We increase the size of the small sequence gradually. And reduce the number of sequences at the same time.
And the sequence waiting for sorting will be more ordered, step by step.
At the last round, we should notice that
we should put all the elements into the array waiting for sorting and use the inserting algorithm in the array.
So we can finish the process of the Shell sorting.
Let’s look at the animation of Shell sorting.
At first, we find two elements. Actually, they cross half of the array.
Then compare them.
In the next round, we double the number of elements.
Which means elements are handled by insert sort in groups of 4.
At last round,
We put all the elements in an array and use the inserting algorithm.
We can see that number of compare and remove is not no big at last round.
Because it is mostly ordered on the top of former work. The whole process of sorting is finished.
Let’s look at the frame of Shell sorting with delta is divided by 2 every loop
We set delta as n/2 at first. which means element are sorted in groups of two at first.
At the next round, the delta is decided by 2,and then do this operation every loop, until the delta is less or equal to 1.
we have delta subsequences in total.
we use inserting sorting in every subsequence notice here, this parameter is passed as the beginning address of first element of the sequence.
the second parameter is passed as the number of available elements.
and we have removed the first elements of subsequence which have been handled.
Which also means the array only can reach the subscript : n-i.
And the inserting sorting use delta as logical step length.
Only elements which distance between it and beginning element can be exactly divide by step length would be sorted.
Finally, you should noticed that if the last sorting can’t be guaranteed,
make all the elements sorted in one process of sorting.
You have to add this. It’s the inserting sorting with delta = 1. It sorting the whole sequence.
In the frame we just mention,
the last sorting can be guaranteed. delta would equal to 1 one time before the whole loop over. And it will sort all the elements.
This is the frame of inserting sort after our modification.
We start at element whose subscript is equal to delta.
the subscript of it’s previous element is : i = 0.
And this limit is the limit you pass in.
The array use delta as step length. So we get a logical subsequence.
when we handle the subsequence waiting for sorting.
we look forward form position i. and jump with step length which is equal to delta,
until we meet an element who is smaller than the element i which is waiting for sorting.
and the element j+1 is the next element.
It should bigger than the element waiting for sorting.
And element i should stay between this two elements.
If we find this position, we can break to out. If not, we can continue to find
and the value of element i has been exchange to position whose subscript is j gradually.
so we continue to move forward until we find the right position or we come to the beginning position
Obviously, Shell sorting is unstable, because the element often cross many elements.
When we handle the logical subsequence, there may be some big jump.
It’s cost of memory is theta(1).
Because we only use a temporary variable when we swap elements.
AS for cost of time, if delta is divide by 2 every time, the cost still is theta(n^2). It’s very inefficient.
we can change the sequence of delta to make the cost of time lower.
Let’s consider this modification. Why is it inefficient when the delta is divided by 2 every round?
Actually, it’s obvious that the deltas we choose are not co-prime.
Like 45 and 34’ we just look.They are at the same sequence this round,
and at next round, they are still at the same sequence.
Which makes the operation of compare is inefficient. Which also means they are compared and handled last round, and we still handle and compare them now. This is why the algorithm is inefficient.
In order to increase efficiency,we should make deltas co-prime.
Like the prior sequence, it is consist of k power of 2, k-1 power of 2, …
Which means there is multiple relationship within them.
If we change the sequence a little, make it becomes k power of 2 minus 1, k-1 power of 2 minus 1.
Then the multiple relationship could be break. Some of them are co-prime.
Further, we can use the way which delta is divide by 3.
These two ways are shell(3) and Hibbard delta sequence(minus 1). Their cost of time both are theta(n^1.5)
We can get lower cost with other delta sequences.
Like sequence consist of (p power 2) times (p power 3). It’s cost is theta(nlogn)
At last, we will left you with several problems.
The first is this. In the inserting sorting, once we find unordered pair, we exchange them ,Rather than move the data when we find the right position.
In addition, we use dichotomy to find the right position rather than compare one by one previously.
We should consider the function of delta in Shell sorting.
Then we research the sequences with delta equal to 2 and delta equal to 3. Which one is better, why?
Besides, we use the inserting sorting every in the every round, can we replace it with other methods?
Thank you!