Algorithm learning-merge sort

Let’s start with Algorithms and Data Structures by Prof. Bobo.Coding.imooc.com/class/71.ht…I sincerely recommend it.

When we solve a problem, there are usually two steps: the first step is to solve the problem, the second step is how to better solve the problem. The second step is to look at the original method based on the first step, whether there is any improvement or optimization, or whether there is a better way to solve the problem. In order to solve the sorting problem, the previous chapter mainly introduces O(n^2) time complexity of the basic sorting algorithm, selection sorting, insertion sorting, and bubble sorting, which is the first step to solve the problem. The three sorting algorithms can solve the problem of sorting, but there is also insufficient, the efficiency is too low, we the amount of data in front of only eight elements, may soon have the result on the computer, perhaps only a few nanoseconds, but when the amount of data is millions or must level, because the time complexity is O (n ^ 2), to undergo two traversal, The time cost of multiples of millions or tens of millions of data is huge. So on a large amount of data, what is the time to use these three sorting algorithms? Prepare a test case to calculate the performance of the three sorting algorithms on 1 million data.

Algorithm performance test

The following function creates a random array of elements of type int, range [rangeL,rangeR], and number n.

    int *generateRandomArray(int n, int rangeL, int rangeR){
        int *arr = new int[n];
        srand(time(NULL));
        for (int i = 0; i < n; i++) {
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        }
        return arr;
    }
Copy the code

The following function checks whether the elements in the array are ordered. The order is set to the smallest to the largest. Basic logic loops through the array until the current element is larger than the next, indicating that the array is not ordered, and returns false.

    template <typename S>
    bool isSorted(S arr[],int n){
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] < arr[i+1]) {
                return false; }}return true;
    }
Copy the code

The following function is the main test function, passing in a string as the first argument, passing in the name of the sorting algorithm, easy to view when printing out. The second argument is a pointer to a function that takes two arguments: the first is the array to be sorted and the second is the number of elements in the array. The next two parameters are the array to be sorted and the number of arrays to be sorted, which are used to pass in function calls.

    template <typename T>
    void testSort(string sortName,void(*sort)(T arr[], int i),S arr[],int i){
        clock_t startTime = clock();
        sort(arr,i);
        clock_t endTime = clock();
        assert(isSorted(arr, i));
        cout<<sortName<<":"<< (double)(endTime - startTime) / CLOCKS_PER_SEC<<"s"<<endl;
    }
Copy the code

The global logic calls the sorted function between startTime and endTime. After sorting, isSorted() is called to test the sorted array. If false is returned, an exception is thrown. Print the difference between endTime and startTime in seconds (s).

Let’s test how long it takes these three functions to sort a million numbers by passing the sorting function we wrote in the previous chapter into the test function.

So the number of arrays that were passed in here, n, was originally 1 million, but after I run it, I wait a long time and I don’t know when it’s going to go. So it’s 100,000. You can see that the bubble sort took 36 seconds, much more than the 11.7 seconds for selection and 8 seconds for insert sort. The reason is that when sorting, a large number of pairs of adjacent elements are exchanged. The exchange takes time, so it takes more time than the previous two kinds of sorting. Bubble sort also has a lot of optimizations, but I won’t go into them here. As you can see, insert sort takes the least time. When we implement insert sort, we create a temporary space to hold the elements to be sorted, avoiding some swapping. For those who don’t quite understand here, you can read my last article: juejin.cn/post/684490… In the optimization section of this article on insertion sort. When creating more temporary space to assist sorting, and exchanging space for time, it becomes another way to consider sorting. In this direction, merge sort and quicksort are two advanced sorting methods with time complexity of 0(Nlogn). This chapter mainly introduces merge sort. Before introducing, let’s briefly compare the time advantage of designing an algorithm with O(nlogn) over 0(n^2).

O of nlogn compared to 0 of n^2 in time

So you can see that as n gets bigger and bigger, or as the order of magnitude gets bigger and bigger, The Times that N logn is running faster and faster than n^2, which is the time ratio, gets bigger and bigger, and when n is 100,000,nlogn is 6020 times faster than n^2. For example, if nlogn takes one day to run, then an n^2 algorithm takes 6,020 days, 365 days a year, and 17 years. If the order of magnitude were larger, the difference in time would be even more pronounced. So it is necessary to design a more efficient sorting algorithm. Let’s start with merge sort, which is more efficient.

The realization idea of merge sort

Also given an array to sort, 8 elements.

The idea of merge sort is to split the array into two parts, and let the two parts sort separately first. And then I’m going to merge these two parts. The entire array is divided into two parts, one is 3,6,4,1, and the other is 8,5,7,2.

In order to sort these two parts, the two parts are cut separately.

And then we’re going to continue to slice and merge. We see that the array is sliced into individual elements. Each element is ordered without having to be sorted. Once you’ve cut it, the next step is to merge it from the bottom up.

Merge begins. 3 and 6 merge into an ordered set of data, 4 and 1 merge into an ordered set of data, 8 and 5 merge into an ordered set of data, 7 and 2 merge into an ordered set of data, the red part of the picture represents each of the small parts of the merge. And you can see that the red is down here and the blue is where the two groups of data merge and become ordered.

And then 3,6 merges with 1,4, 5,8 merges with 2,7, so 1,3,4,6 merges, 2,5,7,8 merges

Go ahead and merge the two parts into a whole.

So the whole red area is sorted. So that’s the idea of merge sort. You divide each part into two parts, and then you sort each part, and then you merge it into an ordered whole. But the point is, what does this merge process look like? If so, then we can use a recursive process that first cuts through the level by level merge to complete the sorting.

Select the last step of the merge process to explain.

The merge process

If you look at the figure below, the left and right parts are sorted, and the merging process is to merge the two parts into an ordered whole. Let’s walk you through merging.

Start by creating a temporary space the same size as this array to help us do this.

So now we’re going to use three indexes to track the elements in the array. Compare the first element pointed to by the yellow arrow in the two sections of the temporary space created.

The 1 on the left and the 2 on the right, I call that the element to be sorted, and then I compare those two elements, 1 is less than 2, so I put 1 on the top of the green arrow in the original array, and it turns red, which means it’s sorted.

1 is already sorted, so I’m going to move the yellow arrow one bit back, pointing to 3, and the first element in the array above, 1, which is red, is already sorted, so I’m going to move the green arrow back. Are shown.

2 is smaller than 3, so put 2 in the position indicated by the array above, and the 1 and 2 in the red area will be sorted. Are shown.

Continue, after 2 is sorted, move the yellow arrow to the right of the temporary space back one bit to the element 5 to be sorted. Because 2 is sorted, point the green arrow of the original array to the next location.

Compare 3, where the two yellow arrows point, to 5, 3 is less than 5, so put 3 where the green arrow points.

Moving on, the green arrow moves back one bit, and the yellow arrow on the left needs to move back one bit, pointing to the next element to be sorted, 4.

Continue the comparison. 4 is less than 5, so put 4 under the green arrow.

After 4 is sorted, the corresponding yellow arrow points to the next element to be sorted, 6. The green arrow moves back to pick up the next element to be placed.

Continue the comparison. 5 is less than 6. Put 5 under the green arrow.

5 after sorting, the yellow arrow moves back to the next element to be sorted 7, and the green arrow moves back to take over the next element to be placed.

Continue the comparison. 6 is smaller than 7, so put 6 under the green arrow.

At this point, elements 1, 3, 4, and 6 on the left are all sorted. So the 7 and 8 elements on the right should be placed directly in the rest of the element. Sorting done.

Summary of sorting process: first open up a temporary space with the same size as the array to be sorted, compare the elements in the two sorted arrays in this space one by one, and place the smaller elements in the corresponding position of the original array.

Code implementation

In the previous illustration, we set up three index locations, which must be clearly defined in code implementation, especially for boundary conditions. So you don’t have a problem coding.

As shown in the figure, the positions of the three indexes are defined as I,j, and k respectively. I,j represent the two elements currently being compared, and k represents where the result of the comparison between the two elements will be placed. It is important to note here that k does not represent the position of the element placed after merging, but rather the next position to be placed. As we write the algorithm, we need to maintain these variables all the time, so that they always meet the definition of what they represent as the algorithm runs.

Next we are going to do some boundary cases. We are going to set the array to be in a pre-closed and back-closed interval, with the left-most position of the array being L (left) and the right-most element being R (right). So the interval of this array is [L,r];

Next, define a variable m(middle) to distinguish between the sorted part on the left and the sorted part on the right. It is defined as: the position of the last sorted element on the left, as shown in the figure.

Therefore, the sorted interval on the left is [L,m], and the sorted interval on the right is [m + 1,r], so the value range of I is 0 <= I <= m; m + 1 <= j <= r;

With these variables defined, let’s write the implementation code:

Again, it is a function that takes the array to be sorted and the number of elements in the array. As you can see from the above implementation, merge sort is essentially a layer by layer recursive process. An implementation of merge sort calls __mergeSort as a recursive function

template <typename T>
void mergeSort(T arr[], int n){
    __mergeSort(arr,0,n - 1);
}
Copy the code

Let’s move on to the implementation of recursive functions. The arguments passed in are the indexes of the leftmost and rightmost elements of the array, so sort the elements in the range arr[l,r].

First, we will deal with the recursion to the bottom, that is, when l >= r, l > r cannot happen, that is, when l = r, since the interval [l,r] is closed before and then closed, there is only one element in the interval, then our recursive function will simply return, otherwise, Define an intermediate variable M, and divide the interval into left and right parts according to m, which represents the last sorted element on the left. Then the interval ranges of the two parts are [L,m] and [m+1,r] respectively. Then call this function to recursively sort the elements within the range of the two parts. The two parts are then recursed, and when the two parts are sorted, the call __merge() merges the two parts.

Template <typename T> void __mergeSort(T arr[], int l,int r){if (l >= r) {
        return; , } int m = (l + r) / 2; __mergeSort(arr, l, m); __mergeSort(arr, m + 1, r); __merge(arr,l,mid,r); }Copy the code

Merge arr[l…m], arr[m+1…r], arr[m+1…r]. Let’s look at the implementation of this function step by step.

• Create a temporary auxiliary array temArr, because the boundary of the array is closed front and closed back, so the size of the array is r-L, we need to add 1.
• The for loop then assigns to the elements in the temporary array. Note that the newly created element index starts at 0 and the array passed in starts at L, so the assignment has an offset of L.
• Define two variables I and j. Represents two elements that are currently being compared between the left and right parts.
• In the comparison sort in the for loop,k represents the final position of the result of the comparison between the elements I and j, and the range of k is the overall range of the two arrays to be merged, namely arr[l,r].
• I is less than or equal to m at most. When I is greater than m, it means that the left part has been sorted. Then the rest of the sorted part on the right is directly assigned to the rest of the unsorted part of ARR. Similarly, j is at most less than or equal to r. When j is greater than R, it means that the sorted part on the right side has been completed. Then the sorted part on the left can be assigned to the unsorted part of ARR.
• Then compare the size of the elements on both sides, assign the small value to arr[k], and then maintain the definition of I and j. The merging process is now complete.

//arr[l...m] and arr[m+1...r] merge the elements of the two arrays. Template <typename T> void __merge(T arr[],int l,int mid,int r){// Create a temporary space T temArr[r-l+ 1];for (int i = l; i<=r; i++) {
        temArr[i-l] = arr[i];
    }
    
    int i = l,j = mid + 1;
    for (int k = l; k <= r; k++) {
        
        if (i>mid) {
            arr[k] = temArr[j-l];
            j++;
        }else if (j>r) {
            arr[k] = temArr[i-l];
            i++;
        } else if (temArr[i-l] < temArr[j-l]) {
            arr[k] = temArr[i-l];
            i++;
        } else {
            arr[k] = temArr[j-l]; j++; }}}Copy the code

Merging algorithm performance test

Using the previously written test cases, the performance test of the written merge sort algorithm is carried out, and the test data volume is the same as the previous 100,000, to compare the difference with the basic algorithm.

As you can see, merge sort takes 0.02 seconds. Performance is 580 times faster than selection sort, 396 times faster than insert sort, and 1,796 times faster than bubble sort. The difference is obvious.

Okay, so that’s it for merge sort, I haven’t talked about optimization of merge sort yet, but I’ll do that later.

Thank you for seeing the end. It’s a little long. I’m not sure if you can understand what I tell you. If there are any errors in the content of this article, please correct them. If you like my article, please follow me.