Of Stack

Java implements the bubble sort algorithm and a simple optimization example for it

  • 2020-05-09 18:41:37
  • OfStack

The principle of

Bubble sort is probably the algorithm all programmers use, and one of the most familiar.
The idea is not complicated:
Let's say I want to sort the array arr[], which has n elements.
1. If n=1: obviously no need to row. (actually, this discussion doesn't seem necessary.)
2. If n > 1:
(1) we start with the first element and compare every two adjacent elements. If the former element is larger than the latter, the former element will be the last in the final result. So let's swap these two guys. Then compare the next two adjacent elements. This is done until the last one compares the elements, and the first sorting is complete. You can be sure that the last element, 1, is the largest in the array (because the relatively large one is always left behind).
(2) repeat the above process, this time we do not need to consider the last one, because it has been arranged.
(3) and so on until there is only one element left, which must be the smallest, and then our sorting is over. Obviously, we did n-1 sorting.
In the above process, each time (or "round") sort will have a number slowly "float" from a certain position to the final position (draw a diagram and draw the array vertically to show it), just like bubble 1, so it is called "bubble sort".

Code implementation: 


public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  // Most do n-1 Trip to sort 
       for(int j = 0 ;j < score.length - i - 1; j++){  // For the current unordered interval score[0......length-i-1] sorting (j The scope is critical, and it is getting smaller )
         if(score[j] < score[j + 1]){  // I'm going to swap the smaller values to the back 
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print(" The first " + (i + 1) + " Sub-sorting results: ");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print(" Final sorting results: ");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

 
Algorithm performance/complexity
We ignore the loop variable increment and initialization time. First, the comparison times of the algorithm are analyzed. It is easy to see that the bubble sort above, without any improvement, does n-1 rounds regardless of the input data, and the number of comparisons per round decreases from n-1 to 0. So the total number of comparisons is (n-1)+(n-2)+... + 2 + 1 = n (n - 1) / 2 material (n ^ 2) / 2. (since I don't know how to square it here, here I'm going to use n^2 for square, same as below)
Let's look at the number of assignments. The assignment here refers to the swap operation. For the above code, 1 swap equals 3 assignments. Because it is not necessary to exchange each time, the number of assignment operations is related to the input data. In the best case (best case), where 1 begins in order, the number of assignments is 0. In the worst case (worst case), the number of assignments is (n-1)n/2. Assuming an average (or "completely random") distribution of the input data, there are approximately one and a half times as many exchanges as there are comparisons. From the above results, we can get that the average case (average case) is 3/2 *(n^2)/2 = 3/4*(n^2).
To sum up, the bubble sort space complexity (extra space) is always O(1) in all cases.

To improve the
When the data is completely ordered, the optimal time complexity is shown as O(n). In other cases, it's almost always O(n^2). Therefore, the algorithm has the best performance when the data are basically in order.
But how can the above code have O(n) complexity? In fact, since the above focuses on the basic idea, it is only the simplest case. In order to achieve the complexity of O(n) in the best case, it is necessary to make some improvements. The code after the improvement is as follows: 


public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { //  The length you need to sort each time 
    swap=false;
    for (int j = 0; j < i; ++j) { //  From the first 1 Elements to the first i An element 
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

In fact, since bubble sort is rarely used for large amounts of data, adding Boolean variables when using small amounts of data results in additional overhead. Therefore, I think the above improved algorithm is purely theoretical. In general, bubble sort can be written as the first one.

Algorithm stability
It's easy to see that when adjacent elements are equal, we don't have to swap their positions, so bubble sort is a stable sort.

Algorithm applicable scenario
Bubble sort idea is simple, the code is simple, especially suitable for small data sort. However, due to the high complexity of the algorithm, it is not suitable for large data. If 1 is to be used with more data, it is better to improve the algorithm, such as selection sort.

Related articles: