Prevention of data overflow in coding

Writing the right code is technology. Writing beautiful code is art.

I was looking at the sorting algorithm two days ago. When I saw merging sorting, I found a coding skill.
Let me review it first. Let's merge and sort it first.
Analysis: the idea of divide and rule is adopted in merging and sorting. A large problem is decomposed into several subproblems. The subproblem and the original problem are solved in the same way, and the subproblem is independent, that is, there is no relationship between subproblems, and the smallest subproblem is solvable and easy to solve. Do you really want to learn about recursion.

Divide and conquer is a way to solve problems, and recursion is a coding skill.

In this way, unsorted data is divided into two parts, and then the two parts are sorted. As for the data divided into two parts, they are treated as the original problems. According to the just thought, the data is divided into two parts orderly until the data size is unique.

That is: merge the ordered subsequences to get the completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly.

Take is cheap .Show me the code .

Code

import java.util.Arrays;

public class MergeSort {

   public static void main(String[] args) {
       int n = 100;
       int [] a = new int[n];

       for(int i = 0;i<n;i++){
           a[i] = (int)(Math.random()*n);
       }

       System.out.println(Arrays.toString(a));
       mergeSort(a,0,a.length-1);
       System.out.println(Arrays.toString(a));
   }

   public static void mergeSort(int[] A,int p ,int r){
       /*Merge sorting is an effective sorting algorithm based on merge operation.
       This algorithm is a typical application of Divide and Conquer.
       The ordered subsequences are combined to get the completely ordered sequences;
       That is, first make each subsequence orderly, and then make the subsequence segments orderly
       Algorithm description:
       The input sequence of length n is divided into two subsequences of length n/2;
       The two subsequences are sorted by merging;
       Merge two sorted subsequences into a final sorting sequence.
                   * */
       if(p >= r)
           return ;
       //Prevent (r+p) overflow
       int q = p + (r - p)/2;

       mergeSort(A,p,q);
       mergeSort(A,q+1,r);

       merge(A,p,q,r);


   }

   private static void merge(int[] A, int p, int q, int r) {
       int i = p;
       int j = q+1;

       int []temp = new int[r-p+1];
       int index = 0;
       while(i <=q && j <=r){
           // Need to be < = equal sign to ensure stability
           if(A[i] <= A[j]){
               temp[index++] = A[i];
               i++;
           }else{
               temp[index++] = A[j];
               j++;
           }
       }

       //To judge whether there is surplus on one side only or not, first assume that there is surplus in the first part
       int start = i;
       int end = q;

       // See if there's any surplus in the second part
       if(j <= r){
           start = j;
           end = r;
       }



       //Remaining copies
       while(start <= end){
           temp[index++]  = A[start++];
       }

       //Copy the temporary array to (p, r) of A
       for( i = 0;i<r-p+1;i++){
           A[p+i] = temp[i];
       }
   }

}

Part of the code

// Take the middle position q between p and r to prevent the sum of (p+r) from exceeding the maximum value of int type
int q = p + (r - p)/2;

When I saw it, I found that I had never thought of such a problem before.
Is it not as usual that int q = (r+p)/2;? It doesn't take into account the size of the data given to you, but when you operate it, you unconsciously enlarge it, and some problems may occur.

May we all be able to achieve certain growth on our own and "grow in a certain way" in the face of external uncertainties.

Tags: Java

Posted on Tue, 03 Dec 2019 13:36:33 -0800 by depsipher