Date: 2021/03/07

preface

In this article, we will briefly review the basic idea of Bubble Sort, focusing on the optimization of Bubble Sort.

The simplest bubble sort

The basic idea of bubble sort is to compare two adjacent elements in sequence, and if the first is larger than the second, swap them; Otherwise, continue the comparison. After one round of comparison, the largest element can be placed at the back, and then the remaining elements can be compared in turn. The final ordered sequence can be obtained through n-1 rounds of comparison at most.

This article uses ascending sorting as an example.

For example, for a group of elements values=[11,10,4,28,24,12,13,16], the process of comparing adjacent elements from front to back is shown in the figure below:

After a round of comparison, the final position of the maximum element 28 is determined, and then the same operation can be repeated for the first seven numbers.

This is the simplest bubble sort algorithm, is also the core of understanding the bubble sort idea, the implementation code is as follows:

/** * The simplest bubble sort is O(n*n) **@param values
    */
public static void sort(int[] values) {
    int i = 0, j = 0;
    for (i = values.length - 2; i >= 0; --i) {
        for (j = 0; j <= i; j++) {
            if(values[j] > values[j+1]) {int temp = values[j];
                values[j] = values[j+1];
                values[j+1] = temp; }}}}Copy the code

With this understanding of bubbling above, let’s start thinking about optimizing bubbling sort.

Optimization of bubble sort

Optimization 1: Timely stop losses

Bubble sort has a major drawback: in the process of sorting, it is unnecessary to compare an already ascending sequence. In this case, the algorithm should be terminated in time to reduce the number of bubbles.

How do you decide if it should be terminated? All we need to do is determine whether an exchange operation was performed during the bubbling process (set a Boolean variable to indicate whether the exchange was performed). If there is no exchange, it indicates that the sequence is ascending, and we can terminate the algorithm.

Once again, after two rounds of switching, we can terminate the algorithm.

Optimization 2: Reduce the number of comparisons

Optimization 1 is to determine whether all unsorted elements are ordered, based on this, we can further optimize.

For all unsorted elements, it may not be ordered, but you can skip the comparison of elements at the end if they form an ordered sequence. In other words, we only need to compare the elements before the last interchange during the bubble.

This idea also includes the case of optimization 1. In optimization 1, the last switch position is 0.

For example, for values=[10,11,4,13,24,12,14,16],24 is ranked last after the first round of comparison. In the second round of comparison, the last recorded exchange position is 3, which is the position of the yellow element 12 in the figure. In the third round of comparison, only the elements before 12 can be compared.

If we were to optimize 1 and only determine whether an exchange occurred, the third round of comparison would still compare to elements before 16.

AC code

public static void bubbleSort(int[] values) {
    int i = 0, j = 0;
    for (i = values.length - 2; i >= 0; --i) {
        /** 1. The tailSortedFlag is used to record the position of j at the last switch of each trip. If the tail is locally ordered, then only the elements before the last switch are ordered. * The initial value of the tailSortedFlag is used to handle the already sorted cases. For different ways of writing bubble sort, the initial value is different. In this case, it is 0 */
        int tailSortedFlag = 0;
        for (j = 0; j <= i; ++j) {
            ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
            if (values[j] > values[j + 1]) {
                SortUtils.swap(values, j, j + 1);
                /** 3. Record the following current position */ for each exchangetailSortedFlag = j; } } i = tailSortedFlag; }}Copy the code

conclusion

The best time complexity of bubble sort is O(n)(if the sequence itself is ordered), the worst time complexity is O(n*n)(if the sequence and the final goal is reversed), and the average time complexity is O(n*n).

The space complexity is O(1). It’s a stable sorting algorithm.

Bubble sort is not very efficient, but what matters to any algorithm is the idea, and the optimization process also improves our ability to design and analyze the algorithm.

This article is participating in the “Nuggets 2021 Spring Recruiting activity”, click to see the details of the activity