Sort algorithm – bubble sort

Introduction to the

Bubble Sort is a simple sorting algorithm in the field of computer science. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted. The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

Time complexity

O(n^2)

Analysis of sorting principle

Analysis of ideas:

Pairwise comparisons. If the preceding element is larger than the following, then the comparison is made to the last element. The next round excludes the elements in order, and the pairwise comparison continues. If the first element is larger than the last, the comparison is switched until only two elements remain, and the sorting is complete.

Sorting rules: Sort from smallest to largest

Array to sort: int[] arr = {-1, -3, -2, -6, 5, 2, 80, 49}

Why not compare round 8, because there are 8 numbers, and round 7 determines the sorted positions of the 7 numbers, so the sorted position of the last number must be correct.

Code implementation

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {-1, -3, -2, -6.5.2.80.49};

        bubbleSort(arr);

        System.out.println(Arrays.toString(arr));
    }


    public static void bubbleSort(int[] arr) {
        int temp;

        boolean flag = false;

        for (int i = 0; i < arr.length - 1; i++) {
            for (int k = 0; k < arr.length - 1 - i; k++) {
                if (arr[k] > arr[k + 1]) {
                    temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                    flag = true; }}// If flag is false it means that there is no swap in this round. You don't have to compare, you just get out of the loop
            if(! flag) {break;
            }
            flag = false; }}}Copy the code

Running results:

[-6, -3, -2, -1, 2, 5, 49, 80]

conclusion

It’s a two-by-two comparison, from front to back, and then at the end of the first round you’ve got the largest element, and you put it at the end of the array. The second largest round determines the next-to-last element, placed in the second-to-last position of the array. The third round determines the third largest element, placed third from the bottom. Each big round excludes the previously sorted elements, loop through the large round of array length -1, then determine the sorting position of the elements of array -1, because the array length -1 elements are sorted, so the last element must be the smallest. So that’s sort.