preface

This time we introduce the bubble sort in swap sort, and simple insertion sort, although bubble sort time complexity is O(n^2), but for ordered array sort, time complexity can also be reduced to O(n), the efficiency is relatively high.

Bubble sort

Sort array [1, 4, 3, 2, 5, 6, 7, 8] from smallest to largest using bubble sort as follows:

  1. Compare the size of adjacent elements in turn.
  2. If the data in front is greater than the data in the back, the two data are swapped, then moved one step to the right, and then compared. After the first round of multiple comparison exchanges, the largest data is moved to the end.
  3. And so on, after n cycles, the array is sorted.

The following figure shows the bubbling sort process:

Bubble sort code:

public static void sort(Comparable[] arr) {
    int n = arr.length;
    for (int i = n; i > 0; i--) {
        for (int j = 1; j < i; j++) {
            if (arr[j - 1].compareTo(arr[j]) > 0) {
                swap(arr, j - 1, j); }}}}private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
Copy the code

Optimization of 1

If bubble sort is used for an ordered array, n(n-1)/2 times is also performed. In fact, every comparison in the inner loop that doesn’t reverse order — that is, swap elements — indicates that the array is in order, and you can exit the program.

The optimization idea is to set an exchange flag swapped, as long as the exchange occurs, let swapped = true, the external loop to determine whether swapped is true, not end the program, indicating that the sorting is complete.

Here is the process of optimizing your thinking:

Optimized code:

public static void sort(Comparable[] arr) {
    int n = arr.length;
    boolean swapped = false;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1].compareTo(arr[i]) > 0) {
                swap(arr, i - 1, i);
                swapped = true; }}// Each for loop puts the largest element in the last position
        // So next time we sort, we can forget about the last element, n--
        n--;
    } while (swapped); 
}

private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
Copy the code

Optimization of 2

On the basis of the above optimization, we can further optimize.

For array: [1, 4, 3, 2, 5, 6, 7, 8], according to the above optimization ideas, we need to compare 5, 6, 7, 8 in the first round of comparison, and 5, 6, 7 in the second round of comparison, but they are ordered, so can we reduce these unnecessary comparisons? The answer is yes.

The idea is that after each cycle, you update the value of n to the last swap, so that everything after that is already in order, so that you don’t have to compare the next cycle.

The following figure shows the process of optimizing your thinking:

Optimized code:

public static void sort(Comparable[] arr) {

    int n = arr.length;
    int newn;
    do {
        newn = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1].compareTo(arr[i]) > 0) {
                swap(arr, i - 1, i);
                // Record the last swap position, after which all elements are already in order, so the next scan will not be considered
                newn = i;
            }
        }
        n = newn;
    } while (newn > 0);
}

private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
Copy the code