Bubble sort

Learning objective: To master the principles and ideas of bubble sorting algorithm

First, premise knowledge

Sorting algorithm concept, time complexity. You can go to this website to learn the sorting algorithm 01_ algorithm basic introduction to read

Two, bubble sort introduction

Exchange sort of bubble sort is a simple sorting, it will repeat visits to sort sequence, compare, compare two elements at a time, if qualified, exchange, every experience a repeat visit, all elements in the sequence will be close to their place, and there must be one of the elements is already arranged. That’s how the algorithm gets its name: in a single arrangement, all the elements move closer to their positions, like bubbles rising from under the water

Third, bubbling sort design idea

So we know from the introduction that bubble sort is going to go through the element that it’s going to sort through every time it’s going to sort

  • You need to control two loops, the innermost loop for accessing the elements to be sorted, and the outermost loop for deciding how many times to repeat the execution

Compare two elements at a time, then

  • Only a temporary variable is needed to aid the exchange

For each repeat visit, the last element in the sequence must be the largest/smallest, so

  • We don’t need to figure out what’s behind the order

Example of bubble sort

Incrementing the following sequence is required: {3,2,5,1,7,9,8}

package com.migu.sortingAlgorithm;

/** * bubble sort */
public class BubbleSort {
    public static void main(String[] args) {
        int a[] = {3.2.5.1.7.9.8};
        
		// There are 7 elements in the column, so the bubble algorithm needs to repeat 6 times to get all the elements sorted to the specified position, so -1
        for(int i = 0; i < a.length-1; i++){// Why (a.length-1), we are comparing by array index +1. You just have to go to the second to the last, and you get the first to the last
            / / or an array will produce ArrayIndexOutOfBoundsException
            // We don't need to judge the sorted elements anymore, so we can subtract -i
            for(int j = 0; j < (a.length-1)-i; j++){if(a[j] > a[j+1]) {int temp = a[j]; // Create a temporary variable to assist the operation, save anyone can achieve the purpose of exchange
                    a[j] = a[j+1];
                    a[j+1] = temp; }}}for(int i : a){
            System.out.printf("%d ",i); }}}Copy the code

Output:

Fifth, the optimization of bubble sort

Through the introduction, we know that bubble sort will repeatedly access the sequence to be sorted, so if it has a repeat access, it does not produce a sort, that means that the sequence is already ordered, there is no need to repeat the sort. So we can add a label

package com.migu.sortingAlgorithm;
/** * Bubble sort optimization */
public class BubbleSort {
    public static void main(String[] args) {
        int a[] = {3.2.5.1.7.9.8};
        boolean flag = true;  // Used for marking
        for(int i = 0; i < a.length; i++){for(int j = 0; j < (a.length-1)-i; j++){if(a[j] > a[j+1]) {int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = false;   // When this code is not executed in a loop, the sorting can be terminated prematurely}}if(flag == false){
                flag = true;   // Set true again to see if the next loop is false, or Over if not
            }else {
                break; }}// Iterate through the sorted loop
        for(int i : a){
            System.out.printf("%d ",i); }}}Copy the code

The time complexity of bubble sort

To discuss the time complexity of an algorithm, we usually look at the worst case:

If you can’t see it, the bubble sort algorithm is O(n^2). If the array has 1000 elements, the inner loop has to repeat 1000 times. 1000^2 is 1 million. Is the worst case probably more than half a million times.

If you’re lucky enough, it’s linear order O(n), but do you think it’s possible in real development ~~~~

Seven,

Each time bubble sort is repeated, all the elements in the sequence get closer and closer to where they want to be, and one element must be already sorted