Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

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


Suddenly an idea, to implement a “elegance” series, the scope of cover is our common several algorithms, yesterday is a beginning, has realized the dichotomy lookup, take a look at today bubble sort, later there will be selection sort, insertion sort, quick sort, hope this series can be let everybody to common algorithm has a simple and clear understanding. Don’t be cool, just do it.

Without further ado, let’s look at bubble sort.

The premise

Given a non-empty array A, it is required to turn a into an ascending array.

Algorithm description

  1. If a[j] > a[j+1], then the two elements are swapped and the comparison is called a bubble round. The result is that the largest element is ranked last
  2. Repeat until the array is in order

The description of the algorithm is pretty simple, but there are a lot of pitfalls in the implementation. Let’s look at the basic implementation first, and then think about optimization.

Algorithm implementation of the basic version

I mentioned above that you get a maximum value at the end of the bubble round. Let’s start with a round of comparisons

for(int j = 0; j < a.length - 1; j ++) {
  if(a[j] > a[j+1]) {
    swap(a, j, j+1); }}Copy the code

How many rounds do we need to compare? Compare as many rounds as the array has elements. Add one more outer loop. Easier, right? So let’s look at the basic implementation.

    private static void bubble(int[] a){
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - 1; j++) {
                if(a[j] > a[j+1]) {
                    swap(a, j, j+1); }}}}private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
Copy the code

Here, the inner loop controls the comparison of each round (a total of A. length-1 times, which is denoted as N), and the outer loop controls how many elements bubble. There should be a small problem here. Does each element need to be compared n times? Obviously, no, the largest element is put at the end of the first bubble. So we can optimize the inner comparison like this.

      for (int j = 0; j < a.length - 1 - i; j++) {
          if(a[j] > a[j+1]) {
              swap(a, j, j+1); }}Copy the code

The above optimization is still relatively easy to understand, let’s think about how to optimize, optimization is nothing more than two aspects, one is to reduce the number of bubbles, the other is to reduce the number of comparison of each bubble.

Now consider an extreme scenario where a given array is ordered. What happens? The outer layer keeps looping, the inner layer doesn’t actually call swap once, but the problem is, if there’s no swap in the first pairwise comparison, the array is already sorted, we don’t need the outer layer to keep looping.

Algorithm optimization version

    private static void bubble(int[] a) {
        for (int i = 0; i < a.length; i++) {
            boolean swapped = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if(a[j] > a[j+1]) {
                    swap(a, j, j+1);
                    swapped = true; }}if(! swapped) {break; }}}private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }    
Copy the code

Here seems to have very great, we have, the number of bubbles above the number of comparisons, and each time the bubbling need are optimized, but that’s enough, don’t we can also compare the number of times to do further optimization, bubbling each round, the last time exchange index can be used as the next bubble is the number of times, if the value is 0, To prove that the entire array is ordered, just exit the outer loop.

In other words, we want to continue the bubbling, depends on the inner loop, if an exchange, then orderly array, exit can directly, if the inner loop exchanged only once, and the location of the exchange is the number of comparisons we need the next bubble, if exchanged twice, then we will take the position of the later as the next bubble is the number of times, I don’t know if this explanation will make sense to you.

For example, a = [5,3,1,9] after the first bubble: 3159, the last position exchanged j is equal to 2 and the next bubble only needs to be compared 2 times. It took me a while to understand this, but when I think about it, IT still feels a little bit, because if I didn’t swap in the last round, it means that everything behind is in order, and naturally there is no need to compare in the next round. Where the previous round of bubbles compare, the next round of bubbles compare there. Last round bubble no comparison, prove array order, exit directly.

Algorithm to achieve the ultimate version

    private static void bubble(int[] a) {
        int loopCount = a.length - 1;
        while(true) {
            int lastIndex = 0;
            for (int j = 0; j < loopCount; j++) {
                if(a[j] > a[j+1]) {
                    swap(a, j, j+1); lastIndex = j; }}if(lastIndex == 0) {
                break; }}}private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
Copy the code

To sum up, I hope I’ve made bubbling sort clear. If you have a better solution, please leave a comment.