Divide and conquer thought - Merge and quick sort

Regular nagging
  • Stability and correctness of the algorithm: sometimes the sorting algorithm will involve stability. First, stability is a statement about whether the position of elements has changed on the premise that the algorithm is correct. If an algorithm operation ends and the initial position between two elements remains unchanged in the final sequence, it is stable.
  • Youmu has a little friend who has seen aha, algorithm before. Come and exchange ideas
Merge
  • Idea: 1. Merging is always called two-way merging. Why is it two-way merging, not one-way merging and three-way merging? That is to say, this algorithm has two lines to sort every time. 2. What is merging? I don't care how many ways you go. In the end, I need a result. Therefore, all people must come together.
  • Key points: 2 roads are sorted at the same time; Merge the two roads; First, decompose one way step by step. When merging, call the parameters (decompose the second way)
  • The road map of the meeting: the world will be divided for a long time, and the world will be divided for a long time. The two ways will be merged and fully withdrawn. Assuming that the original sequence has five small country elements, I now want to arrange the order of strength. Can't you let my No. 1 country play one by one and engage in wheel tactics one by one? And this kind of popular ranking, of course, the faster the better. Therefore, first divide into groups, then divide into groups, then eliminate the strong and weak, and finally merge.
  • Points for attention in problem solving: 1. Synchronization of opening and closing: unsorted can be opened and closed, and only ordered subsets can be combined; 2. When merging, pay attention to the remaining elements after subset size judgment; 3. Open up a new space to receive the combined set;
Two way code - core idea
    public static int[] sort(int[] sourceArray) {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //Only one element
        if (arr.length < 2) {
            return arr;
        }
        // Take out the intermediate node that divides the whole into two channels
        int middle = (int) Math.floor(arr.length / 2);

		// Recursive subsets - stepwise fission
        int[] left = sort(Arrays.copyOfRange(arr, 0, middle));
        int[] right = sort(Arrays.copyOfRange(arr, middle, arr.length));
		// Merge, and gradually collect subsets by changing the length of the recursive array
        return merge(left,right);
    }
Merge code
 public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        // Merge sorted two subsets
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
		// If the size of the two arrays is compared, after sorting and merging, the left array still has the remaining elements larger than the previous elements, and the remaining elements are directly added to the merge set
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }
		// If the size of the two arrays is compared, after sorting and merging, the right array still has the remaining elements larger than the previous elements, and the remaining elements are directly added to the merge set
        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }
Quick sort
  • Idea: the reason why merging is fast is that multiple channels are engaged in at the same time; Why is quick sort fast? I don't have many ways to go, but I can go one way A - > b, or B - > A. I'm driving at both ends at the same time. It's not like bubbling or inserting. I can only be A - > B In the communication transmission, it seems to be simplex. When optimizing the communication channel, it will be said that simplex will be changed into half duplex or full duplex. I understand that quick sorting is simplex - > duplex optimization.
  • The road map of the meeting: because the left and right sides start at the same time, we need a rule: what do the left parents do and what do the right parents do. Because it is the major premise of sorting, it is: select a cardinality. The one on the left is larger than the cardinality and the one on the right is smaller than the cardinality. Then, there is a general scope: that is, all larger or smaller subsets can be obtained according to the established cardinality. PS: whichever side is bigger and which side is smaller, in fact, it's all in ascending or descending order. Then repeat the same steps in their respective subsets.
  • Key points: cardinality and subset reordering (recursion)
  • Key points: maintenance of critical points of subset in the original array; No new space is opened. Pay attention to the maintenance of the original array
code
  public static int[] quickSort(int[] arr,int l,int r){

        // Determine the reference value of one operation
        int base = arr[l];
        int lindex = l,rindex=r;
        while (lindex<rindex){
            // Find the first position less than the reference value from right to left
            while (arr[rindex]>base && lindex<rindex){
                rindex--;
            }
            // Find the first position larger than the reference value from left to right
            while (arr[lindex]<base && lindex<rindex ){
                lindex++;
            }

            // In the middle position, a round of operation has not ended yet, and the exchange is carried out
            if(lindex<rindex && arr[lindex]!=arr[rindex]){
                int temp = arr[rindex];
                arr[rindex]=arr[lindex];
                arr[lindex]=temp;
            }
            //Moving the lvalue pointer to the right, or moving the right pointer to the left, is sufficient
            if(lindex<rindex && arr[lindex]==arr[rindex]){
                lindex++;
            }
        }

        // Reordering before partition
        if(l<lindex-1){
            arr = quickSort(arr,l,lindex-1);
        }
        if(rindex+1<r){
            arr = quickSort(arr,rindex+1,r);
        }

        return arr;
    }
A little immature idea
  • Under the thought of partition and rule, quick platoon and merging have the same merit. Will be divided into subsets. The difference lies in the division rules of subsets and the characteristics of the divided subsets. In addition, whether there is an application for new space.
  • I should have been scared silly.

Posted by gorgo666 on Sun, 08 May 2022 13:59:23 +0300