This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Split insertion sort

For direct insertion sort, every time the position k to be inserted is searched, it needs to be searched from the back to the front. The search process can be improved by half-fold search, that is, half-fold insertion sort, which is inefficient

Insert sort code in half

void  InsertSort(ElemType  A[],int  n){
int  i,j,low,high,mid; 
for(i = 2; i<=n; i++){ A[0]=A[i]; 
low=1; high=i- 1; 
while(low<=high){
mid=(low+high)/2; 
if(A[mid].key>A[0].key)
high=mid- 1;
else
low=mid+1;
for(j=i- 1; j>=high+1; --j)
A[j+1]=A[j]; 
A[high+1]=A[0]; }}Copy the code

Note:

  • Compared with direct insertion, half-cut insertion only reduces the number of comparison of elements, and the average comparison of any element changes from O(n) to O(logn).
  • The average number of moves per element in the halfway insertion sort algorithm is still O(n).
  • So the average time complexity of half-cut insertion is (logn+n)*n=O(𝑛2).
  • Halfway insertion sort is a stable sorting method
  • Half-insert is only suitable for sorted tables that are stored sequentially

Hill sorting

Hill sort, also known as reduced incremental sort, has the following basic ideas:

① Take a step size d1 less than n and split the table into d1 special sub-tables L[I],L[I +d]… ,L[i+kd]

② Use direct insertion sort for each subtable to ensure the order of each subtable

③ Shorten the steps d1 to d2 and repeat ①②

④ After repeated ③ several times, the whole table element is “basically in order”, only need to insert all records directly once

Hill sort code

void  ShellSort(ElemType  A[],int  n){
for(dk = n/2; dk>=1; dk=dk/2)     // Step size changes
for(i =dk+1; i<=n; ++i)if(A[i].key<A[i-dk].key){    // Insert A[I] into the ordered augmented quantum table
A[0]=A[i];
for(j=i-dk; j>0&&A[0].key<A[j].key; j = j-dk)
A[j+dk]=A[j];         A[j+dk]=A[0]; / / insert}}Copy the code

Note:

  • Space efficiency: use only constant replication units, space complexity is O(1)
  • Time efficiency: Because the step size D will affect time efficiency, the strict proof of the corresponding time complexity has not been determined mathematically. It is generally considered to be about O(𝑛1.3) and the worst time complexity is O(𝑛2) through tests.
  • Applicability: Hill sort is only applicable when linear tables are stored sequentially and stability is not required

Class extension”

9.2.2 Split insertion Sort

The basic operation of direct insertion sort is to use the order to find the insertion position of the current record in the ordered table, of course, can also use the semicircution search (bisection search) method to locate, the corresponding sorting method is called semicircution sort.

To compare the records to be inserted with the middle records in the ordered table by keyword, the ordered table is split into two. The next comparison is performed in one of the ordered sub-tables, and the sub-tables are split into two again. This continues until there is only one record in the child table to compare, and the insertion location is determined by a single comparison. The algorithm is as follows.

[Algorithm 9-2] The algorithm of halfway insertion sort

The algorithm is analyzed as follows.

(1) Time complexity.

In terms of time complexity, using half-broken insertion sort can reduce the number of keyword comparison. In the half-way search for determining the insertion position, the comparison times needed to locate the position of a keyword are at most the depth of the half-way decision tree, so the time complexity of the comparison times is O(nlog2n). The number of moving records in half insertion sort is O(n2), which is the same as that in direct insertion sort.

On average, half-insert sort only reduces the number of keyword comparisons, while the number of record moves remains the same. Therefore, the time complexity of half-cut insertion sort is O(n2).

(2) Spatial complexity.

The auxiliary space required by split insertion sort is the same as that required by direct insertion sort, only one auxiliary unit R [0] is used, and its space complexity is O(1).

The algorithm features are as follows.

(1) is a stable sorting method;

(2) only applicable to sequential storage structure, can not be used for chain structure;

(3) It is applicable to the case where the initial record is out of order and n is large.

9.2.3 Hill sort

The direct insertion sorting algorithm is simple and efficient when n is small. When the value of n is large, if the sequence to be sorted is basically ordered according to keywords, the efficiency is still high, and its time efficiency can be increased to O(n). Hill sort gives an improved method of insertion sort based on the two points of “reducing the number of records” and “basic order of sequence”.

Hill sorting, also known as narrowing the incremental sorting, was founded in 1959 by D.L.S hell, hill sorting idea is: first, choose a smaller than n integers di (called step), then the order n record in a table is divided into di group, starting from the first record, interval for di records for the same group, each group within the direct insertion sort. After one run, the records of interval DI are in order. With the improvement of orderliness, the step size di is reduced and repeated until di=1, so that the records of interval 1 are in order, that is, the ordering expression is in order.

Known for 9-2 】 【 collating sequence for {39,80,76,41,13,29,50,78,30,11,100,7,41 *, 86}, step length factor di take 5,3,1 respectively, with hill sorting algorithm implementation process is given.

Figure 9-2 shows the Hill sorting process.

Figure 9-2 Example of hill sorting process

The hill sort algorithm is as follows.

[Algorithm 9-3] Hill sorting algorithm

The algorithm is analyzed as follows.

(1) Time complexity.

From the perspective of time complexity, when the increment is greater than 1, the record with small keyword jumps, so that the sequence is basically in order when the last insertion sort with increment of 1, and only a small amount of comparison and movement can complete the sorting. Therefore, the time complexity of Hill sort is lower than that of direct insertion sort.

It is very difficult to analyze the efficiency of Hill sorting time. The comparison times of keywords and the number of record movements depend on the selection of step size factor DI sequence. In specific cases, the comparison times of keywords and the number of record movements can be accurately estimated. At present, there is no method to select the best step factor sequence.

Based on a large number of experiments, the number of comparison and movement required by Hill’s sorting is about N1.3 when n is in a certain range, and can be reduced to O(N log2n)2 when n goes to ∞.

(2) Spatial complexity.

The auxiliary space required by Hill sort is the same as that required by direct insertion sort, only one auxiliary element R [0] is used, and its space complexity is O(1).

The algorithm features are as follows.

(1) is an unstable sorting method;

(2) only applicable to sequential storage structure, can not be used for chain structure;

(3) Step size factor di can be taken by various methods, including odd number and prime number, but it should be noted that there should be no common factor except 1 in step size factor, and the last step size factor must be L;

(4) The total number of comparison and movement in the algorithm is less than that of direct insertion sort. When n is larger, the time efficiency effect of the algorithm is more obvious. This is applicable when the initial record is out of order and N is large.