C++ insertion sort algorithm example details

In this paper, the example for you to share C++ insertion sorting algorithm instance of the specific code, for your reference, the specific content is as follows

The basic idea

Insert one element at a time, one at a time, into the appropriate position of the sorted subsequence by its size, until all the elements have been inserted.

Direct insertion sort

1. Sorting ideas

arr[0... i-1] is the ordered region (at the beginning, i=1, arr[0] has only one element), arr[i...size] is the ordered region. Every time, the first element of the ordered region, arr[i], is inserted into the proper place of the ordered region.

2. Sorting algorithm

void InsertSort(int* arr, int size) 
{ 
  if (arr == NULL) 
    return; 
 
  for (int i = 1; i < size; i++) 
  { 
    //1. Save the number to sort  
    int tmp = arr[i];   
    //2. Go to the ordered region to find where the number should be inserted  
    int j = i - 1; 
    while (j >= 0 && tmp < arr[j]) 
    { 
      //3. So let's take the ordered area 1 a 1 A back  
      arr[j + 1] = arr[j]; 
      j--; 
    } 
    arr[j + 1] = tmp; 
  } 
} 

3. Algorithm analysis

The direct insertion sort is composed of two loops, and the outer loop is n-1 times.
If the initial data sequence is in an increasing order, it is positive order. The sorting does not enter the inner loop every time, and the size comparison is conducted only once. At this point, the element moves twice (tmp = arr[i] and arr[j+1] = tmp). Therefore, The Times of positive sequence time comparison and The Times of element movement both reach the minimum values Cmin and Mmin:

Cmin = n-1
Mmin = 2 (n-1)

If the initial data sequence is in reverse order, the elements in the current ordered region are all larger than those in the to-be-sorted region, so it is necessary to compare the elements to be inserted with all the elements in arr[0... i-1], which requires i comparison. In the inner loop, all elements in arr[0... i-1] are moved back (i-1) -0+1 = i times, plus two moves of tmp = arr[i] and arr[j+1] = tmp, and the number of element moves required for one sorting is i+2 times. Therefore, the comparison times and element movement times in reverse time both reach the maximum da values of Cmax and Mmax:

Cmax = n(n-1) / 2
Mmax = (n-1)(n+4) / 2

The time complexity of direct insertion sorting algorithm in positive sequence is O(N), and that of direct insertion sorting algorithm in reverse sequence is O(N^2).
Therefore, the time complexity of direct insertion sort algorithm is O(N^2). Since only three auxiliary variables, i, j and tmp, are used, the space complexity is O(1).
When i > When j [i] = arr[j] and arr[i] = arr[j], arr[i] is directly inserted into arr[j], so the direct insertion sort is stable.

Half insertion sort (2 points insertion sort)

1. Sorting ideas

The insertion position is first found in arr[0... i-1] using a binary search method, and then inserted by moving the element
2. Sorting algorithm

void InsertSort1(int* arr, int size) 
{ 
  if (arr == NULL) 
    return; 
 
  int i, j, low, high; 
  //1. Save the number to insert  
  for (i = 1; i < size; i++) 
  { 
    int tmp = arr[i]; 
    low = 0; 
    high = i - 1; 
    //2. Fold half to find the insertion position ( The insertion position is high+1) 
    while (low <= high) 
    { 
      int mid = low + ((high - low) >> 1); 
      if (tmp < arr[mid]) 
        high = mid - 1; 
      else 
        low = mid + 1; 
    } 
    //3. The element moves back and inserts  
    for (j = i - 1; j >= high + 1; j--) 
    { 
      arr[j + 1] = arr[j]; 
    } 
    arr[j + 1] = tmp; 
  }   
} 

3. Algorithm analysis

When the initial data sequence is positive, the comparison times cannot be reduced. When in reverse order, the number of comparisons does not increase. Element movement is the same as direct insertion sort.
Therefore, the time complexity of half-insertion sort is O(N^2), and the space complexity is O(1), which is stable.
On average, binary search is better than sequential search, so binary insert sort is better than direct insert sort.

Hill sorting

1. Sorting ideas

Hill sort is a grouping insertion sort. First, take 1 integer d1 less than n, as the first increment, the sequence is divided into d1 group. All the elements with multiple distances of d1 are put into the same group, and the sequence is directly inserted into each group. And then I take the second increment, d2 ( < d1), repeat the process until the increment is 1.
Hill sort does not produce an ordered region in each run. Before the last run, all elements do not return to their original positions. After each run, the data gets closer and closer to the ordered region.

2. Sorting algorithm

void ShellSort(int* arr, int size) 
{ 
  if (arr == NULL) 
    return; 
 
  int i, j, gap; 
  //1. take gap 
  gap = size / 2; 
  while (gap > 0) 
  { 
    //2. Grouping is  
    for (i = gap; i < size; i++) 
    { 
      int tmp = arr[i]; 
      //3. Move the element, insert  
      j = i - gap; 
      while (j >= 0 && tmp < arr[j]) 
      { 
        arr[j + gap] = arr[j]; 
        j -= gap; 
      } 
      arr[j + gap] = tmp; 
    } 
    gap = gap / 2; 
  } 
} 

3. Algorithm analysis

The performance analysis of hill sorting algorithm is a complex problem. Its time complexity is related to gap. Generally speaking, the time complexity is O (N ^ 1.3) and the space complexity is O (1).
Hill sort is an unstable algorithm.