Direct insertion sort
The idea of direct insertion sorting is: Insert the records to be sorted into an ordered sequence that has been sorted one by one according to the size of their key code values, until all the records are inserted.
, get a new ordered sequence .
We can first look at the one-pass process of figuring out direct insertion sort (ascending):
Let’s insert a number 6 into an ordered sequence, end is positioned at the end of the sequence, and compared with the number x to be inserted, if a[end]>x, end will move forward one bit, and a[ end] Move one bit to the back.
The insertion of the number 6 belongs to an ordinary insertion (inserted into the middle of the sequence). Let’s now try the insertion of number 1 (insert into the head of the sequence).
After figuring out the insertion of these two situations, we can probably write a single-pass process of direct insertion sorting.
//Single-pass process of direct insertion sort
void InsertSort(int* a, int sz){
int end;//The position at the end of the ordered sequence
int x;//Number to be inserted
while(end>=0){
if(a[end]>x){
a[end + 1]=a[end]
end--;
}
else {
break;
}
}
a[end + 1]=x;
}
After we figure out the single-pass process of direct insertion sorting, we are now thinking about how to sort a given set of sequences by direct insertion? That is how to control the position of the end and x we write.
We first set the position of end to 0, and set x to the position of end + 1, which is equivalent to sorting the numbers before end, and then inserting the numbers after end into the sequence before end. This completes the complete process of direct insertion sort.
void insertSort(int* a, int sz) {
for (int i = 0; i < sz - 1; i ++ ) {
int end = i;
int x = a[end + 1];
while (end >= 0) {
if (x < a[end]) {
a[end + 1] = a[end];
end--;
}
else {
break;
}
}
a[end + 1] = x;
}
}
The worst case of the time complexity of direct insertion sorting is O(N^2), which is the case where the sequence is inserted in descending order and the values are sorted in ascending order.
The best case of time complexity is O(N), and the case of inserting values into a sequence in ascending order is in ascending order.
Hill sort
Hill sort is an optimization of direct insertion sort. We also mentioned just now that the best time complexity of direct insertion sorting is O(N), and the sequence at this time is a sequence that is close to order. Hill sorting is to pre-sort the sequence to make the sequence close to order, and then use direct insertion sorting.
How does Hill Sort perform pre-sorting?
First, the sequence is grouped by gap, and the grouping is directly inserted and sorted to make the sequence close to order.
If we set the value of gap to 3, then the above sequence will be divided into 3 groups, and each group will be directly inserted and sorted.
Let’s figure out how one of the groups completes the direct insertion sort. Let’s take the first group as an example.
We set end to the position of 0, x is the position of end + gap (that is, the next position of the group), if a[end]>x, move a[end] to the next position in the group, and end is set to the previous position in the group.
void ShellSort(int* a, int sz) {
int gap = 3;
int end = 0;
int x = a[end + gap];
while (end >= 0) {
if (a[end] > x) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = x;
}
In this way, we have completed the direct insertion sorting in a single group. We noticed that this is very similar to direct insertion sorting. When gap=1, it is the logic of direct insertion sorting. Now we need to control end to implement single-group sorting.
We observe the above figure, each group of red, green and blue, the last element of each group is behind the n-gap, and the cycle is controlled by the principle of direct insertion sorting as follows, then the direct insertion sorting of a single group can be completed.
for (int i = 0; i < sz - gap; i + = gap)
For the rest to complete the multi-group sorting, you need to control i.
for (int j = 0; j < gap; j ++ )
for (int i = j; i < sz - gap; i + = gap)
Based on the above analysis, we can write the following code to complete the preview:
void ShellSort(int* a, int sz) {
int gap = 3;
//Complete preview
for (int j = 0; j < gap; j ++ ) {
for (int i = j; i < sz - gap; i + = gap) {//i + = gap is a group of rows
int end = i;
int x = a[end + gap];
while (end >= 0) {
if (a[end] > x) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = x;
}
}
Above we wrote two loops to complete the pre-sorting of Hill sort, and below we use one loop to complete the pre-sorting of Hill sort. Let’s go to the code first, and then explain it in detail.
//Complete the preview
for (int i = 0; i < sz - gap; i + + ) {//i + + is multiple groups side by side
int end = i;
int x = a[end + gap];
while (end >= 0) {
if (a[end] > x) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = x;
}
If we carefully observe the above code, we will find that we have only one change, that is, i + = gap becomes i + +;
i + = gap means that one group is finished, and then the next group is arranged.
And i ++ is to arrange multiple groups at the same time. Let’s see the diagram below for details.
When i is equal to 0 to 2, there is only one number in the three groups of red, green and blue, which are compared with the next number of each group and inserted. When i is greater than 2, the i-th digit is compared with the ordered number in the range [0, end] in each group and inserted. The numbers whose positions have moved in the figure below are marked with light green circles. At first glance, it is rather vague, I hope to calm down, the logic here is not entangled.
The results here are walkthrough results only. It is the first step in Hill sorting, generating a relatively ordered sequence.
After pre-sorting, we can control the change of gap to complete the logic of Hill sorting. Come on, everyone!
The larger the gap, the faster the pre-sorting is, and the less orderly it is after the pre-sorting
The smaller the gap, the slower the pre-arrangement, and the closer to the order after the pre-arrangement
gap=1 is direct insertion sort
Here we can understand that when we press gap=3, the result is 5 1 2 5 6 3 8 7 4 9
And when we gap=1, the result is an ordered sequence 1 2 3 4 5 5 6 7 8 9
void ShellSort(int* a, int sz) {
int gap = 3;
while (gap > 1) {
gap /= 2;
//Complete preview
for (int i = 0; i < sz - gap; i + + ) {//i + + is multiple groups side by side
int end = i;
int x = a[end + gap];
while (end >= 0) {
if (a[end] > x) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = x;
}
}
}
We control the change of the gap according to the method of gap /= 2;, and the result will become smaller and smaller, and finally it will be 1, so that we can make a sequence close to order, and then arrange it according to the direct insertion sort of gap=1. The time complexity is close to O(N). But the time complexity of Hill sort is actually O(N^1.3).
Hill sorting is an excellent sorting algorithm, which is suitable for use when the amount of data is large.