C language to achieve sorting algorithm merge sort details

  • 2020-04-02 02:23:50
  • OfStack

Merge Sort in sorting algorithm is the use of "Merge" technology to Sort. Merge is the merging of several sorted subfiles into an ordered file.

I. realization principle:

1. Basic ideas of the algorithm

Suppose two ordered subfiles (equivalent to the input heap) are placed in adjacent positions in the same vector: R[low..m], R[m+1..high], merge them into a local temporary vector R1(equivalent to the output heap), and copy R1 back into R[low..high] after merging.

(1) merger process

During the merge, set the three Pointers I, j, and p, whose initial values point to the starting positions of the three record areas respectively. When merging, compare the keywords of R[I] and R[j] in turn, copy the record with a smaller keyword into R1[p], and then add 1 to the pointer I or j of the copied record and 1 to the pointer p to the copied location.
Repeat this process until one of the two input subfiles has been copied (call it empty), then copy the remaining records from the other non-empty subfile to R1 in turn.
Finally, assign the result to R[] in.

(2) apply R1 dynamically

R1 is applied dynamically when implemented, because the application space may be large, so the application space must be included in the successful processing.

Ii. Three methods:

Algorithm 1: merge functions dynamically allocate an array, and merge two ordered arrays into an ordered array


//Merge combines two ordered sequences ([low,mid],[mid+1,high])
void Merge(int arr[],int low,int mid,int high)
{
  int i=low,j=mid+1,p=0;

  int *newarr = (int *)malloc((high-low+1)*sizeof(int));//To store sorted data temporarily
  if(!newarr){
    printf("malloc error!n");
    exit(1);
  }

  while(i<=mid && j<=high){    //The following process is similar to merging two ordered strings into one ordered string
    if(arr[i] < arr[j])
      newarr[p++] = arr[i++];
    else
      newarr[p++] = arr[j++];
  }

  while(i<=mid)
    newarr[p++] = arr[i++];
  while(j<=high)
    newarr[p++] = arr[j++];

  for(i=low,p=0;p<(high-low+1);i++,p++)  //Copy the result into the original array
    arr[i] = newarr[p];
  free(newarr);
}

Method 2:

Dynamically allocate a large array at the beginning of the program to avoid creating many small arrays at a time.

For assert() see: (link: #)



#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static void merge1(int array[], int tmp[], int lpos, int rpos, int rend);
static void msort1(int array[], int tmp[], int left, int right);

void merge_sort1(int array[], int n)
{
 assert(array!=NULL && n>1); //If the condition is not satisfied, exit the program and print the error statement.

 int *tmp = (int *)malloc(sizeof(int) * n);
 assert(tmp != NULL);
 int i;
 for (i = 0; i < n; i ++) {
 tmp[i] = array[i];
 }
 msort1(array, tmp, 0, n-1);

 free(tmp);
}

//Recursively call this function, to achieve half partition, only partition, not to achieve sorting, and finally return array[] array in order
static void msort1(int array[], int tmp[], int left, int right)
{
 assert(array!=NULL && tmp!=NULL);

 if (left == right)
 return;

 int center = (left + right) / 2;
 msort1(tmp, array, left, center);
 msort1(tmp, array, center+1, right);
 merge1(tmp, array, left, center+1, right);
}

//This function implements a sorted array of the left and right halves of array[], merging them into TMP [], and sorting them
static void merge1(int array[], int tmp[], int lpos, int rpos, int rend)
{
 assert(array!=NULL && tmp!=NULL);

 int lend = rpos - 1;
 int tmp_pos = lpos;

 while (lpos<=lend && rpos<=rend) {
 if (array[lpos] <= array[rpos])
  tmp[tmp_pos++] = array[lpos++];
 else
  tmp[tmp_pos++] = array[rpos++];
 }

 while (lpos <= lend)
 tmp[tmp_pos++] = array[lpos++];
 while (rpos <= rend)
 tmp[tmp_pos++] = array[rpos++];
}

int main(int argc, char *argv[])
{
  int a[7] = {6, 5, 4, 3, 2, 1, 7};

  merge_sort1(a, 7);
  int i;
  for (i = 0; i < 7; i ++) {
    printf("%3d", a[i]);
  }
  printf("n");

  return 0;
}

Method 3:
A large array is allocated at the beginning of the program, but each time array[] is used to order the data to TMP [], and finally TMP [] is assigned to array[], so that the entries are the same for each call.


void merge_sort1(int array[], int n)
{
 assert(array!=NULL && n>1); //If the condition is not satisfied, exit the program and print the error statement.

 int *tmp = (int *)malloc(sizeof(int) * n);
 assert(tmp != NULL);
 int i;
 for (i = 0; i < n; i ++) {
 tmp[i] = array[i];
 }
 msort1(array, tmp, 0, n-1);

 free(tmp);
}

//Recursively call this function, to achieve half partition, only partition, not to achieve sorting, and finally return array[] array in order
static void msort1(int array[], int tmp[], int left, int right)
{
 assert(array!=NULL && tmp!=NULL);

 if (left == right)
 return;

 int center = (left + right) / 2;
 msort1(tmp, array, left, center);
 msort1(tmp, array, center+1, right);
 merge(tmp, array, left, center+1, right);
}

Implementation method 2:


void merge(int array[],int tmp[],int lpos,int rpos,int rend)
{
  int i,leftend,num,tmppos;

  leftend = rpos - 1;
  num = rend - lpos + 1;
  tmppos = lpos;

  while(lpos <= leftend && rpos <= rend){
    if(array[lpos] <= array[rpos])
      tmp[tmppos++] = array[lpos++];
    else
      tmp[tmppos++] = array[rpos++];
  }

  while(lpos <= leftend)
    tmp[tmppos++] = array[lpos++];
  while(rpos <= rend)
    tmp[tmppos++] = array[rpos++];

  for(i = 0;i < num;i++,rend--)
    array[rend] = tmp[rend];
}

Merge sort: merges an unordered array into an ordered array

There are two ways to do this: bottom-up and top-down

1. Bottom-up method (bottom-up merge sort algorithm is more efficient but less readable)

(1) basic bottom-up ideas:

The basic idea of bottom-up is: when the first merge sort, the files to be sorted R[1..n] are regarded as n ordered subfiles of length 1, and these subfiles are merged in pairs. If n is even, n/2 ordered subfiles of length 2 are obtained. If n is odd, the last subfile is null. Therefore, after this merge, the length of the first logn ordered subfiles is 2, but the length of the last subfile is still 1. The second merge is to merge the logn ordered subfiles from the first merge in pairs, and so on, until you end up with an ordered file of length n.
Each merge operation mentioned above is to merge two ordered subfiles into one ordered subfile, so it is called "two-way merge sort". Similarly we have k of k > 2) merge sort.

(2) a merge algorithm
  Analysis:
In a merge, set the length of each subfile to length(the length of the last subfile may be less than length), then R[1..n] has an ordered subfile: R[1..length], R[length+1..2length],...

Note:

When the merge operation is called to merge an adjacent pair of subfiles, special treatment must be given to two special cases: the number of subfiles may be odd, and the length of the last subfile is less than length:

If the number of subfiles is odd, then the last subfile does not need to merge with other subfiles (that is, the cycle);
If the number of subfiles is even, notice that the upper bound of the interval of the last subfile in the last subfile pair is n.

The specific algorithm is as follows:



void MergePass(SeqList R . int length)
{ //Do a merge sort for R[1..n]
  int i;
  for(i=1;i+2*length-1<=n;i=i+2*length)
    Merge(R,i,i+length-1,i+2*length-1);
  //Merge two adjacent subfiles of length
  if(i+length-1<n) //There are two subfiles, the last of which is less than length
    Merge(R,i,i+length-1 . n) ;  //Merge the last two subfiles
//Note: if I  Or less n and I + leng-1  p n, one subfile will be null and need not be merged
} //MergePass

void MergeSort(SeqList R)
{//A two-way merge sort is carried out for R[1..n] by bottom-up method
  int length;
  for(1ength=1;length<n;length*=2) //Do visit to merge
    MergePass(R . length); //Terminated when ordered segment length  p n
}

2. Top-down approach

The top-down algorithm is designed by divide-and-conquer method, which is more concise.

(1) three steps of divide-and-conquer

If the current interval of merge sort is R[low..high], the three steps of divide and conquer are:

(1) decomposition: split the current interval into two, that is, find the splitting point: mid = (low+high)/2;
(2) solution: recursively merge sort the two sub-intervals R[low..mid] and R[mid+1..high].
Combination: merge the two sorted sub-intervals R[low..mid] and R[mid+1..high] into an ordered interval R[low..high].

Closure condition for recursion: subinterval length 1 (a record in natural order).

Specific algorithm:


void MSort(int arr[],int low,int high)
{
  if(low < high){
    int mid = (low+high)/2;
    MSort(arr,low,mid);   //Left half sort
    MSort(arr,mid+1,high); //Right half sort
    Merge(arr,low,mid,high);//Merge left and right halves
  }
}

Three:

1. Stability
Merge sort is a stable sort.

2. Storage structure requirements
You can store structures sequentially. It is also easy to implement on linked lists.

3. Time complexity
For files of length n, it is necessary to merge LGN twice, and the merge time of each time is O(n), so its time complexity is O(n LGN) in both the best and worst cases.

4. Space complexity
An auxiliary vector is needed to temporarily store the merge result of two ordered subfiles, so its auxiliary space complexity is O(n), obviously it is not in place sort.

Note:
If a single linked list is used as a storage structure, it is easy to give in - place merge sort.


Related articles: