Brief analysis of direct insertion sort and half insertion sort

Let's take a look at the example, insert the data one by one into a list, and then the list will be sorted

Note: this list is incrementing, and the memory space is allocated, but the actual data is not populated, as shown in the following code:

int InsertSort(MergeType *L, int data)
{
 int j;
 if (!L->len)
 {
  L->elem[++L->len] = data;
  return 0;
 }
 for (j = L->len-1; j >= 0; --j)
 {
  if (data < L->elem[j])
  {
   L->elem[j+1] = L->elem[j];
  }
  else
  {
   L->elem[j+1] = data;
   L->len++;
   break;
  }
 }
 return 0;
}

The test case code is as follows:

#define  LISTLEN 10 
 MergeType pList;
 MergeType pT;  
 pList.elem = (int*)malloc(sizeof(int)*LISTLEN);
 ScanfList(&pList);
 pList.len  = LISTLEN;
 pList.size = LISTLEN;
 
 pT.elem = (int*)malloc(sizeof(int)*LISTLEN); 
 pT.len = 0;
 pT.size = LISTLEN;
 memset(pT.elem, 0, LISTLEN*sizeof(int));
 for (int i = 0; i < LISTLEN; i++ )
 {
  InsertSort(&pT, pList.elem[i]);
 }
 PrintList(&pT);

 free(pList.elem);
 free(pT.elem);
 pList.elem = NULL;
 pT.elem = NULL;

Other functions and code to define please refer to:

Direct insertion sort

Core idea: is to insert a record into the sorted ordered table, from which a new, the number of records increased by 1 ordered table, that is, the increasing order of each data, each data into the previously sorted position. Look at the code below

int InsertSort(MergeType* L)
{
 int i, j = 0;
 int nCompKey;
 if (!L->elem || !L->len) return -1;

 if (L->elem && (L->len==1)) return 0;
 for ( i = 1; i < L->len; i++) 
 {
  if (L->elem[i] < L->elem[i-1])  
  {
   nCompKey = L->elem[i];
   L->elem[i] = L->elem[i-1];   
   //move elements back
   for (j = i-2; j >= 0 && nCompKey < L->elem[j]; --j) 
   {
    L->elem[j+1] = L->elem[j];
   }
   L->elem[j+1] = nCompKey;
  }
 }
 return 0;
}

Here, we start from the second data and compare whether the current data is less than the previous number. If the current data is less than the previous number, we insert the current data into the previous queue. During the insertion into the previous data, we move the data

Note the complexity of time:

Total number of comparisons =1+2+...... + (I + 1-2 + 1) +... + (n - 2 + 1) = n * (n - 1) / 2 = O (n ^ 2)

Total movement =2+3+...... + (2 + I - 1) +... + n = (n + 2) * (n - 1) / 2 = O (n ^ 2)

Of course, there is also the complexity of space: the storage space of a variable is used as the temporary space for moving data

Here, in the process of moving, the complexity of code understanding can be reduced, but the number of times of comparison will be increased in each process of data comparison, as shown in the following code:

 ...
 if (L->elem[i] < L->elem[i-1])  
 {
  nCompKey = L->elem[i];
  
  for (j = i-1; j >= 0 && L->elem[j] > nCompKey; --j) 
  {
   L->elem[j+1] = L->elem[j];
  }
  L->elem[j+1] = nCompKey; 
 }
 ...

In the process of inserting data, in fact, the previous data have been sorted, at this time, one by one to find, must find more times, if the use of half-cut search algorithm can reduce the number of times, as follows

int BInsertSort(MergeType *L)
{
 int i, j;
 int low, high, mid;
 int nCompKey;
 for (i = 1; i <= L->len - 1; i++ )
 {
  nCompKey = L->elem[i];
  low = 0;
  high = i - 1;

  
  while(low <= high) 
  {
   mid = (low + high)/2;
   if ( nCompKey > L->elem[mid] )
   {
    low = mid + 1;
   }
   else
   {
    high = mid -1;
   }
  }
  
  for (j = i-1; j >= high+1; j-- ) 
  {
   L->elem[j+1] = L->elem[j]; 
  }
  
  L->elem[high+1] = nCompKey;
 }
 return 0;
}

For the specific reason, please refer to the above comment, why high+1 is used here, but at this time, the position of high and low is only one position different, it will break out of the while loop, please see the following improvement

#if 0
  for (j = i-1; j >= high+1; j-- ) 
  {
   L->elem[j+1] = L->elem[j]; 
  }
  L->elem[high+1] = nCompKey;
#else
  for (j = i-1; j >= low; j-- ) 
  {
   L->elem[j+1] = L->elem[j]; 
  }
  L->elem[low] = nCompKey;
#endif
...