Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

0 Basic Version

In all cases the time is O(n2n^2n2).

Public static void Bob (int[] array) {// For (int I = 0; i < array.length - 1; I++) {// for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; }}}}Copy the code

The above algorithm is simple and crude, it is two layers of for for any array.

If you had an ordered array now, such as {1,2,3,4,5,6,7,8}, you would waste CPU unnecessarily. How to avoid it?

We see that if the elements are overall ordered, then in the code above

if (arr[j] > arr[j + 1])
Copy the code

It will never be satisfied, and then there will be no exchange of elements, so we can add a Boolean value to see if there has been an exchange of elements, and if there has not been an exchange of elements, we can just jump out. As follows:

1 Advanced version

A Boolean is added to determine if there is an element exchange, and if there is not, the exchange ends early.

private static void bob2(int[] arr) {
    int length = arr.length;
    for (int i = 0; i < length; i++) {
        boolean swap = false;
        for (int j = 0; j < length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swap = true;
            }
        }
        if (!swap) break;
    }
}
Copy the code

The above code avoids blind sorting of the whole ordered array. However, if an array is not globally ordered, but locally ordered, such as {4,3,2,1,5,6,7,8}, we observe that the second half is not required to be sorted, that is, only the first half is required to be sorted.

So, we have to figure out where the element is ordered, which is the index of the ordered region.

So, how do we determine this subscript?

If we think about bubble sort, we swap if the next element is bigger than the previous one, otherwise we don’t swap, that is, the last place where the swap occurred must be in order. For example, if there is an exchange after I, and there is no exchange after I, then there must be some order after I, otherwise there would be another exchange after I.

So, the last place that each element swapped is the beginning of the index of the ordered region, and the end of the index of the unordered region.

Define a subscript, update the subscript every time there is an element exchange, the elements after the subscript are ordered, each comparison only compares the elements before the subscript.

The code is as follows:

2 Advanced version

private static void bob3(int[] arr) { int length = arr.length; int lastSwapIndex = 0; Int sortedBorder = length-1; for (int i = 0; i < length; i++) { boolean swap = false; For (int j = 0; j < sortedBorder; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swap = true; // Update the index lastSwapIndex = j; }} // update subscript sortedBorder = lastSwapIndex; if (! swap) break; }}Copy the code

The above code can solve the case of partial order but overall disorder.

But it turns out that all of the above code is comparing from left to right, and if the array is {2,3,4,5,6,7,8,1}, that’s partially ordered, but if you compare from left to right, it takes time, and if you compare from right to left, it’s a round.

But! If from right to left, meet {8,1,2,3,4,5,6,7} so kneel again, how to do? We can do a two-way comparison, which is once from left to right, once from right to left, and that’s called cocktail ordering.

Now we use cocktail sort (bidirectional sort), switching directions after each sort, as follows:

3 Final Version (Cocktail Ordering)

private static void bob4(int[] arr) { int length = arr.length; for (int i = 0; i < (length >>> 1); i++) { boolean swap = false; For (int j = 0; j < length - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); swap = true; } } if (! swap) break; // from right to left swap = false; for (int j = length - 1; j > 0; j--) { if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); swap = true; } } if (! swap) break; Private static void swap(int[] arr, int I, int j) {arr[I] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }Copy the code

conclusion

Although bubble sort has been optimized for many times, its time complexity is still O(n2), which is unavoidable, because bubble sort only swaps adjacent elements each time, that is, only one reverse pair is eliminated, and the time complexity of all sorts by swapping adjacent elements is O(n2).

Why is that? Because swapping adjacent elements removes only one pair of inversions at a time. So let’s prove that.

If you’ve taken Linear algebra, you know the definition of inverse.

In a permutation, logarithms are said to be in an inverse order if their front and back positions are in reverse order of magnitude, i.e. the number in front is larger than the number behind. The total number of inversions in a permutation is called the number of inversions of that permutation.

Proof: The time complexity of sorting by swapping adjacent elements is O(
n 2 n^2 )

If any sequence L has n elements, it can form Cn2C_n^2Cn2 pairs (two pairs of elements are selected from n elements), i.e. (n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1)), where the inverse number is A; Then take the reverse sequence Lr, which has the reverse number b, and b= (n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1))-a, because the sequence pairs in L are all reversed pairs in Lr, and for any number pairs, either order or reverse (the same can be considered as order), So a+b= (n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1)).

So, L and Lr total reverse on is n (n – 1) (2) (\ frac {n (n – 1)} {2}) n (n – 1) (2), then the reverse order of a single L on is n (n – 1) (4) (\ frac {n (n – 1)} {4}) n (n – 1), (4), when n tend to be + up, That’s n2n^2n2, and swapping neighboring elements can only eliminate one pair of inversions at a time, so you have to swap n2n^2n2 times, so the time complexity of the algorithm is O(n2n^2n2).

Why does swapping neighboring elements only eliminate one inversion pair, because it only changes the position of the two neighboring elements, whether they are larger or smaller than it, whether they are smaller or smaller than it. For example, {5,4,3,2,1}, we swapped the 3 and the 2 to become {5,4,2,3,1}. We found that, just eliminating {1,2}, the front 5 and 4 are still larger than the two, and the back 1 is still smaller than the two, so we only need to eliminate one pair of inversions.

That’s it.

In fact, we can extend it to say that any algorithm that can only eliminate one pair of inversions at a time is O(n2n^2n2). And no more nonsense.