Introduction to the

Sorting is probably the most basic and common algorithm of all. Sorting is the classic problem of reordering the items in an array (or a list) in a certain order.

There are many kinds of sorting algorithms, each of which has its own advantages and limitations.

Today we are going to learn the simplest bubble sort algorithm.

The principle of bubble sort

The principle of bubble sort is very simple. Let’s imagine bubbles floating up one by one.

Suppose we have eight numbers 29,10,14,37,20,25,44,15 to sort.

Let’s first use an animation to visually observe the entire bubble sort process:

There are eight rounds of sorting, with each round doing a pairwise comparison and moving the larger elements to the right, like bubbling.

At the end of the round, element 44, the largest of the eight elements, will move to the far right.

Then repeat the other rounds. You end up with a fully sorted array.

Or look at it this way:

The first round is to move the swap 44, the largest of the eight elements, to the far right. The second round is to move the swap 37, the second largest of the eight elements, to the far right. And so on.

Java implementation of bubble sort algorithm

Let’s start with the simplest bubbling algorithm:

public class BubbleSort {

    public void doBubbleSort(int[] array){
        log.info("The array before sorting is :{}",array);
        // Loop over all rounds
        for(int i=0; i< array.length-1; i++){
            // Select a larger number and swap
            for(int j=0; j<array.length-1; j++){
                if(array[j]>array[j+1]) {// Switch two numbers
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            log.info("The array sorted by {} round is :{}", i+1, array); }}public static void main(String[] args) {
        int[] array= {29.10.14.37.20.25.44.15};
        BubbleSort bubbleSort=newBubbleSort(); bubbleSort.doBubbleSort(array); }}Copy the code

The algorithm is a two-layer traversal, with the outer layer representing the number of rounds performed. The inner traversal represents the sorting of each round.

Let’s look at the output:

The first improvement of the bubble algorithm

If we look at the traversal above, we can see that after the first sorting, 44 is already on the far right, it’s already sorted.

After the second sorting, 37 is sorted as well. After each round, the number of times the internal loop needs to be compared can be reduced by one.

This means that we only need to make array.length-i-1 comparisons during the inner loop.

Modify the code as follows:

public class BubbleSort1 {

    public void doBubbleSort(int[] array){
        log.info("The array before sorting is :{}",array);
        // Loop over all rounds
        for(int i=0; i< array.length-1; i++){
            // The last I digits are sorted, so no more comparisons are needed
            for(int j=0; j<array.length-i-1; j++){
                if(array[j]>array[j+1]) {// Switch two numbers
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            log.info("The array sorted by {} round is :{}", i+1, array); }}public static void main(String[] args) {
        int[] array= {29.10.14.37.20.25.44.15};
        BubbleSort1 bubbleSort=newBubbleSort1(); bubbleSort.doBubbleSort(array); }}Copy the code

Running results:

As you can see, the results are actually the same, but there are fewer comparisons.

Second improvement of bubble algorithm

From the above results, we can see that the sorting is actually done after round 5. But we still did the sixth and seventh sort.

Is there any way to tell if the sorting is done?

So let’s think about, in the inner loop, we’re doing pairwise comparisons and then switching places.

If there is no interaction during a particular walk, that means the sorting is done.

So we can introduce another flag.

public class BubbleSort2 {

    public void doBubbleSort(int[] array){
        log.info("The array before sorting is :{}",array);
        // Loop over all rounds
        for(int i=0; i< array.length-1; i++){
            // Add a flag. If there is no sorting in this round, the sorting is finished and you can exit early
            boolean flag=false;
            // The last I digits are sorted, so no more comparisons are needed
            for(int j=0; j<array.length-i-1; j++){
                if(array[j]>array[j+1]) {// Switch two numbers
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = true;
                }
            }
            log.info("The array sorted by {} round is :{}", i+1, array);
            if(! flag) { log.info("There is no change in sorting in this round. Sorting is done.");
                return; }}}public static void main(String[] args) {
        int[] array= {29.10.14.37.20.25.44.15};
        BubbleSort2 bubbleSort=newBubbleSort2(); bubbleSort.doBubbleSort(array); }}Copy the code

The running results are as follows:

From the results we can see that there is one less round of sorting, which increases the speed.

Time complexity of bubble sort

Although we can do some performance tuning while bubbling, we still basically do two nested traversals. The number of iterations is approximately =n*n, so the time complexity of bubble sort is O(n²).

The code address of this article:

learn-algorithm

This article has been included in www.flydean.com/algorithm-b…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!