Introduction to algorithms really good (thick) ah, just saw sorting

The sorting

Insertion sort

Insert sort is suitable for a small number of elements.

Cyclic invariant

• Initialization: True until the first iteration of the loop.
• Hold: If it is true until one iteration of the loop, it remains true until the next iteration.
• Termination: When the loop terminates, the invariant gives us a useful property that helps prove that the algorithm is correct.

Code implementation

• ascending

  public static void insertionSort(int[] A) {
      for (int i = 1; i < A.length; i++) {
          int key = A[i];
          int j = i - 1;
          while (j >= 0 && A[j] > key) {
              A[j + 1] = A[j];
              j--;
          }
          A[j + 1] = key; }}Copy the code

• Descending order

  public static void insertionSort(int[] A) {
      for (int i = 1; i < A.length; i++) {
          int key = A[i];
          int j = i - 1;
          while (j >= 0 && A[j] < key) {
              A[j + 1] = A[j];
              j--;
          }
          A[j + 1] = key; }}Copy the code

In the best case, the array is completely or almost ordered, and the time complexity can be reduced to O(n). In the average case, the time complexity is O(n^2^) and the space complexity is O(1).

Note: Using binary lookup during insertion effectively reduces the number of comparisons, but the number of moves remains the same, and the total running time is still O(n^2^) instead of O(n LGN).

Algorithm problem sets

Add two n-bit binary numbers.

public static int[] addBinary(int[] A,int[] B) {
    int[] C = new int[A.length + 1];
    int carry = 0; 
    for (int i = 0; i < A.length; i++) {
        C[i] = (A[i] + B[i] + carry) % 2;
        carry = (A[i] + B[i] + carry) / 2;
    }
    C[i] = carry;
    return C;
}
Copy the code

Merge sort

Merge sort algorithm completely follows divide-and-conquer mode.

• Decomposition: Decompose the sequence of n elements to be sorted into two subsequences with n/2 elements each

• Solution: Sort two subsequences recursively using merge sort

• Merge: Combine two sorted subsequences to produce sorted answers

Code implementation

public static void mergeSort(int[] A,int p,int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(A,p,q);
        mergeSort(A,q + 1,r); merge(A,p,q,r); }}public static void merge(int[] A,int p,int q,int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int[] L = new int[n1 + 1];
    int[] R = new int[n2 + 1];
    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = A[q + j + 1];
    }
    // Set two sentinels
    L[n1] = Integer.MAX_VALUE;
    R[n2] = Integer.MAX_VALUE;
    int i = 0,j = 0;
    for (int k = p; k <= r; k++) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            ++i;
        } else{ A[k] = R[j]; ++j; }}}Copy the code

If sentry is not used in the merge, the code should be modified to read:

public static void merge(int[] A,int p,int q,int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = A[q + j + 1];
    }

    int i = 0,j = 0;
    int k;
    for (k = p; i < L.length && j < R.length; k++) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            ++i;
        } else{ A[k] = R[j]; ++j; }}// Only one of the next two loops will be executed
    while (i < L.length) {
        A[k] = L[i];
        ++i;
        ++k;
    }
    while(j < R.length) { A[k] = R[j]; ++j; ++k; }}Copy the code

Uptime analysis

Decompose: Computes the middle position of the array. The constant is time.

Solution: Recursively solving two subproblems of size N /2 will contribute 2T(n/2) of running time

Merge: Merge takes θ (n) time

The recursion is:

According to the main theorem, the solution of the recurrence formula is:

Algorithm problem sets

Determining whether there are two numbers in the set S of n integers whose sum is exactly x (S, where x is a parameter) requires time complexity O(n LGN).

public static boolean practise(int[] A,int x) {
        mergeSort(A,0,A.length - 1);
        for (int i = 0; i < A.length; i++) {
            if (binarySearch(A,0,A.length - 1,i,x - A[i])) {
                return true; }}return false;
    }

	// merge sort, O(NLGN)
    public static void mergeSort(int[] A,int p,int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(A,p,q);
            mergeSort(A,q + 1,r); merge(A,p,q,r); }}public static void merge(int[] A,int p,int q,int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];
        for (int i = 0; i < n1; i++) {
            L[i] = A[p + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + j + 1];
        }
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;
        int i = 0,j = 0;
        for (int k = p; k <= r; k++) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                ++i;
            } else{ A[k] = R[j]; ++j; }}}// Binary search, time O(LGN)
    public static boolean binarySearch(int[] A,int low,int high,int index,int x) { // Index is passed to ensure that it is not found with the subtracted value (e.g. 8-4 = 4)
        while (low <= high) {
            int mid = (low + high) / 2;
            if(x == A[mid] && mid ! = index) {return true;
            } else if (x < A[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1; }}return false;
    }
Copy the code

Quick sort

Main idea: Same as merge sort. Quicksort also uses the idea of divide-and-conquer.

Process and implementation

• Decomposition: array A [p.. r] is divided into two sub array [p]… q – 1 A and A/q + 1,.. r, including A [p]… q – 1 less than or equal to A [q], A [q + 1 r] that… [q] greater than or equal to A.
• Solve: Sort subarrays A[p… q-1] and A[q + 1,..r] by recursively calling quicksort.
• Merge: Because subarrays are address-sorted, no merge is required: array A[p… r] is already sorted.

Code implementation (Java) :

public static void quickSort(int[] A,int p,int r) {
        if (p < r) {
            int q = partition(A,p,r);
            quickSort(A,p,q - 1);
            quickSort(A,q + 1,r); }}public static int partition(int[] A,int p,int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (A[j] <= x) { If (A[j] >= x)
                i = i + 1;
                swap(A,i,j);
            }
        }
        swap(A,i + 1,r);
        return i + 1;
    }
    public static void swap(int[] A,int i,int j) {
        int x = A[i];
        A[i] = A[j];
        A[j] = x;
    }
Copy the code

Quicksort performance

• Worst-case division

  The worst case of quicksort occurs when two subproblems resulting from partitioning contain n-1 and 0 elements, respectively. The time complexity of partition operation is θ (n²), and the recursion of algorithm running time is

  
  $$T(n) = T(n-1) + T(0) + θ (n) = T(n-1) + θ (n)$$

  The solution can be obtained directly by substitution method

  
  $$T (n) = Θ (n squared)$$

So the time complexity of quicksort is θ (n²) when the input array is completely ordered, but O(n). When the input array is completely ordered.

• Best-case division

  The performance of quicksort is best when neither of the two subproblems produced by partition is larger than N /2. The recursion of the algorithm running time is:

  
  $$T(n) = 2T(n / 2) + THETA (n)$$

  The solution can be obtained by using the master method

  
  $$T (n) = Θ (NLGN)$$

The average case of quicksort is closer to its best case than its worst case.

Special circumstances:

• Case 1:

  QuickSort time complexity is θ (n^2^) when all elements in the array have the same value. Because every partition returns r, dividing the array into subarrays of n-1 and 0. In order for it to return (p + r) / 2 in this case, it can be modified as follows:

public static int partition(int[] A,int p,int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (A[j] <= x) {
                i = i + 1;
                swap(A,i,j);
            }
        }
        swap(A,i + 1,r);
        if (i + 1 == r) {
            return (p + r) / 2;
        } else {
            return i + 1; }}Copy the code

• Situation 2:

  QuickSort time complexity is θ (n^2^) when the elements in the array are in descending order. Since each partition returns p (since both are larger than the hub value), the array is divided into subarrays of 0 and n-1.

• Case 3:

  The time complexity of QuickSort is θ (n^2^) when the elements in the array are mostly in ascending order. Since each partition returns r (because it is smaller than the hub value), divide the array into subarrays of you -1 and n0.

A randomized version of quicksort

The last element of the array is chosen as the primary element. Now, for randomization, we can randomly select an element from A[p..r] as the primary element, which is equally likely to be selected from the array.

Code implementation:

public static void quickSort(int[] A,int p,int r) {
    if (p < r) {
        int q = randomizedPartition(A,p,r);
        quickSort(A,p,q - 1);
        quickSort(A,q + 1,r); }}public static int randomizedPartition(int[] A,int p,int r) {
    Random random = new Random();
    int i = random.nextInt(r - p + 1) + p;
    swap(A,i,r);
    return partition(A,p,r);
}
public static int partition(int[] A,int p,int r) {
    int x = A[r];
    int i = p - 1;
    for (int j = p; j <= r - 1; j++) {
        if (A[j] <= x) {
            i = i + 1;
            swap(A,i,j);
        }
    }
    swap(A,i + 1,r);
    return i + 1;
}
public static void swap(int[] A,int i,int j) {
    int x = A[i];
    A[i] = A[j];
    A[j] = x;
}
Copy the code

The running time of quicksort is determined by the time spent on the partitition operation. A primary element is selected each time a partition is called, and that element is not included in subsequent Quicksort and partition calls. Therefore, at most n partition operations will be invoked.

Each pair of elements in the array is compared at most once and at least 0 times.

Compare once: Because each element compares to the main element, after a partition operation, the main element used in this call will never compare to any other elements.

Zero comparison: Elements divided into two parts are never compared.

The basic idea of counting sort is to determine the number of elements less than x for each input element. Use this information to place x directly at its position in the output array.

Code implementation

public static void countingSort(int[] A,int[] B,int k) {
    int[] C = new int[k + 1];  
    for (int i = 0; i < A.length; i++) {
        C[A[i]]++;
    }
    for (int i = 1; i < k + 1; i++) {
        C[i] += C[i - 1]; // Each element represents each number in the array plus the number of numbers less than or equal to it
    }
    for (int i = A.length - 1; i >= 0; i--) {
        B[C[A[i]] - 1] = A[i]; C[A[i]]--; }}public static int findMaxValue(int[] A) { // to generate k
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < A.length; i++) {
        if(A[i] > max) { max = A[i]; }}return max;
}
Copy the code

Time is O(n + k), space is O(n + k).

Counting sort does not require comparison and is stable, which is important only if the sorted data is accompanied by satellite data. Counting sort is often used as a subprocess of radix sort algorithms.

Reasons for stability

• For example, two elements with equal value A[I] = A[j], where I < j, in the counting process, A[I] in the front is always counted first, and in the subsequent restoration of the array, because it is placed from back to front, the number of elements in the front is less than or equal to it, so its stability can be guaranteed.

If the last loop is not back to front, but instead is front to back, i.e. I = 0 -> a. length-1, the sorting can still be completed, but stability is not guaranteed.

Algorithm development

According to this idea, we can find the number of n input integers falling in the interval [a,b] in O(1) time. The preprocessing stage is the counting stage, and its time complexity is O(n + K).

Code implementation

public static int[] countNumbers(int[] A,int k) { / / pretreatment
    int[] C = new int[k + 1];
    for (int i = 0; i < A.length; i++) {
        C[A[i]]++;
    }

    for (int i = 1; i < k + 1; i++) {
        C[i] += C[i - 1];
    }
    return C;
}
public static int countNumbersOfa_b(int[] C,int a,int b) {
    return C[b] - C[a - 1]; 
}
Copy the code