This is the 10th day of my participation in the August More Text Challenge

Insertion sort

Sorting can be divided into two types according to whether the data elements are completely in memory:

  1. Internal sort: the sort in which all elements are stored in memory during the sort. Both internal sorts perform two operations during execution: compare and move.

  2. External sort: refers to the sort in which elements cannot all be stored in memory at the same time and must be moved between internal and external memory as required during the sort process. External sorting is also concerned with making disk reads/writes less.

The idea of insert sort is to insert one record to be sorted into a previously ordered subsequence by its keyword size at a time until all records have been inserted. The idea of insertion sort can be extended into three important sorting algorithms: direct insertion sort, split insertion sort and Hill sort

Direct insertion sort

The theory of

Direct insertion is a stable sorting method suitable for sequential and chained linear tables. The idea is to insert each element in turn into the corresponding position in the previously sorted child table.

Algorithm implementation

void InserSort(ElemType A[], int n) { int i, j; for(i=2; i<=n; i++) if (A[i] < A[i - 1]) { A[0] = A[i]; for (j = i - 1; A[0] < A[i]; --j) A[j + 1] = A[j]; A[j + 1] = A[0]; }}Copy the code

Split insertion sort

Half-insert sort separates the comparison and move operations, that is, first half-insert to find the position of the element to be inserted, and then uniformly move all elements after the position to be inserted.

Algorithm implementation

void half_Insert(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] > A[0]) 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

Hill sorting

concept

Of hill sorting the basic idea is: first the sorting table divided into shape, such as L [I, I + d, I… I + kd] + 2 d of the “special” child table, separated by a “delta” is the record set a child table, for each child table direct insertion sort, respectively, when the element has the basic order of the entire table, on the whole table again direct insertion sort. In general, the first increment is n= the total number of elements /2;

Algorithm implementation

void shell_Sort(ElemType A[],int n) { int i, j, dk; for (int dk = n / 2; dk >= 1; dk--) for(int i=dk+1; i<=n; i++) if (A[i] < A[i - dk]) { A[0] = A[i]; } for (int j = i - dk; j > 0 && A[0] < A[j]; j -= dk) A[j + dk] = A[j]; A[j + dk] = A[0]; }Copy the code