Bubble sort upgrade [Cocktail sort]

This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Please follow OpenCoder and make friends with me ~❤😘😁🐱🐉 😁

I. Concept of cocktail ordering

Cocktail sort is an upgrade of bubble sort algorithm. Each element in bubble sort can act like a bubble, moving a little bit towards one side of the array, depending on its size. The algorithm compares elements from left to right in each turn, doing a one-way position swap. Cocktail sequencing is based on this element comparison and exchange process becomes two-way. Solid cocktail sort is also known as bidirectional bubble sort, cocktail mixing sort, mixing sort, ripple sort, back and forth sort or happy hour sort, is a kind of deformation of bubble sort.

The worst cocktail sort or the average number of times it takes is O(n ^ 2), but it’s closer to O(n) if the sequence has been mostly sorted at the beginning.

Two. Logical deduction

Problem analysis:

[2,3,4,5,6,7,8,1]

The bubble sort process is as follows:

Results analysis:

It’s inconvenient to sort elements 2, 3, 4, 5, 6, 7, 8 seven times, when all you have to do is put elements 1 in the right place. If I could just change the place of the 1, I’d have an order. Cocktail sequencing is designed to solve this problem.

Optimization idea:

Cocktail details:

First round (same as bubble sort, 8 and 1 swap)

Round 2: This is the beginning of a different, we reverse the comparison from right to left for the exchange.

Round 3: The process is not over, although it is actually orderly.

In the third round of cocktail sorting, the swap needs to be compared from left to right again.

1 and 2 are in the same position; 2 and 3 are in the same position; 3 and 4 are in the same position… 7 and 8 are in the same position. No elements are swapped, prove current order, end of sort.

Summary:

This is the ingenious algorithm of cocktail sorting, which could have taken 7 rounds.

And the idea of cocktail sorting, sorting process is like a pendulum, the first round from left to right comparison, second round from right to left comparison, third round from left to right comparison…

3. Cocktail sorting algorithm

Code:

    public static void sort(int[] array) {
        // Loop count
        int count = 0;
        // Data exchange temporary variables
        int tmp = 0;
        for (int i = 0; i < array.length / 2; i++) {
            System.out.println("The first" + (++count) + "Subcycle");
            // The initial value of each round is true. The order flag is true for order
            boolean isSorted = true;
            // Odd rounds, compare and swap from left to right
            for (int j = i; j < array.length - i - 1; j++) {

                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    // Swap, not order, flag to false
                    isSorted = false; }}// It is in order
            if (isSorted) {
                break;
            }
            // Re-mark isSorted to true before even rounds
            isSorted = true;
            System.out.println("The first" + (++count) + "Subcycle");
            // Even round, direction from right to left compare and swap
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    isSorted = false; }}// It is in order
            if (isSorted) {
                break; }}}Copy the code

Result output:

The first1Loops in the first2Loops in the first3Loops [1.2.3.4.5.6.7.8]
Copy the code

Conclusion:

This code is the original implementation of cocktail sorting. The large loop outside of the code controls all sorting turns and contains two small loops, the first comparing and swapping elements from left to right, and the second comparing and swapping elements from right to left.

Cocktails have the advantage of reducing the number of rounds to sort when most elements are already in order; The disadvantage is also obvious, that is, the amount of code is almost doubled.