Efficiency of bubble sort

This is the 27th day of my participation in the First Challenge 2022. There are two steps to perform bubble sort.

  • Compare: Compare two numbers to see which is larger.
  • Swap: To swap the positions of two numbers so that they are arranged in order.

Let’s see how many comparisons bubble sort takes.

Looking back at the previous five-element array, you can see that in the first iteration we compared four pairs of elements four times.

In the second cycle, only three comparisons were made. This is because the first iteration has already determined the elements of the last cell, so there is no need to compare the last two elements.

The third cycle, only two comparisons; The fourth time, I’m only comparing one time.

It all adds up:

4+3+2+1=10 comparisons.

Generalized toThree elements, required

Once more.

After analyzing the comparison, let’s look at the exchange.

If the array is not just randomly shuffled, but completely out of order, in the worst case, each comparison will be swapped. So 10 comparisons plus 10 swaps, 20 total steps.

Now put the two steps together. An array of 10 elements requires:

9+8+7+6+5+4+3+2+1=45 comparisons and 45 swaps, a total of 90 steps.

With 20 elements, it would be:

19+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+3+2+1=190 comparisons and 190 exchanges, a total of 380 steps.

It’s too inefficient. The number of elements increases exponentially while the number of steps increases exponentially, as shown in the following table.

And if you look a little bit more closely, you’ll see thatThe number of steps increases approximately to2.

So describe the efficiency of bubble sortNotation, it is.

To put it more formally: useAlgorithm to deal withThat’s about two elementsStep.

The algorithm is relatively inefficient. As the data quantity increases, the number of steps increases, as shown in the figure below.

Pay attention toThe curve representing the number of steps is very steep,Is only diagonal.

One final point:Also calledThe second time.