Algorithm defined

Bubble sort is a kind of exchange sort, is a simpler sort algorithm. According to the encyclopedia definition, it repeatedly goes through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong. The work of visiting elements is repeated until no adjacent elements need to be exchanged, that is, the column has been sorted. The algorithm gets its name from the fact that the smaller elements are exchanged and slowly rise to the top of the sequence, just as the bubbles of carbon dioxide in carbonated drinks eventually rise to the top.

Algorithm principle

The principle of bubble sort algorithm is as follows:

1. Compare a pair of adjacent elements. If the first element is larger than the second, swap the pair.

2. Repeat step 1 for all adjacent elements, from the first pair of elements to the last undetermined pair. After this step, determine the largest remaining element.

3. Repeat steps 1 and 2 with fewer and fewer remaining elements until the largest element of all currently remaining elements is determined.

Code implementation

Following the above idea, the preliminary code is as follows:

Public class Main {// bubble sort (exchange sort), O(1) public static void bubbleSort(int[] arr) {for (int I = 0; i < arr.length - 1; For (int j = 0; int j = 0; int j = 0; j < arr.length - 1 - i; ++j) {if (arr[j] > arr[j + 1]) {arr[j] ^= arr[j + 1]; arr[j + 1] ^= arr[j]; arr[j] ^= arr[j + 1]; } } } } }Copy the code

However, the time complexity of the above code is fixed at O(n ^ 2). If the array is already ordered, it is unnecessary to swap the elements again, or if the number of times of swapping the elements becomes ordered halfway through the array, it is unnecessary to swap the elements again. Therefore, the above code is flawed and needs improvement.

Let’s say the array is of length n.

Best case: if the array is ordered, then there is no element exchange. If the first for loop I = 0, then the second for loop is done. After the second for loop ends, the array is determined to be ordered. This process takes only one trip, but there is no element exchange, and each trip takes orders of magnitude n, so the best-case time complexity is O(n).

Worst case: if the array is in reverse order, then n – 1 element exchange is required, and each exchange takes the order of n time, so the worst case time complexity is O(n ^ 2).

Average case: The number of trips in the average case can be expressed as n-1-k, k is constant, and the time of each element exchange is also the order of n, so the average case takes (n-1-k) * n, and the average time complexity is equal to the total time spent/the number of all cases. Because different cases show different steps, so the number of cases is equal to the order of n, and the total time is equal to the time taken by the average case times the number of cases, which is (n-1-k) * n * n, The average time complexity = the total time taken/the number of cases = (n-1-k) * n * n/n = (n-1-k) * n, because k is constant, so (n-1-k) * n is actually the order of n ^ 2, So the average time complexity is order n ^ 2.

According to the above analysis, the improved code is as follows:

Public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main {public class Main} O(1) public static void bubbleSort2(int[] arr) {for (int I = 0; i < arr.length - 1; ++ I) {// Check whether the array is ordered; Boolean flag = true; For (int j = 0; int j = 0; int j = 0; j < arr.length - 1 - i; ++j) {if (arr[j] > arr[j + 1]) {arr[j] ^= arr[j + 1]; arr[j + 1] ^= arr[j]; arr[j] ^= arr[j + 1]; Flag = false; // The array is not in order; }} if (flag) {// If the array is ordered, end the loop break; }}}}Copy the code

The algorithm efficiency

Bubble sort is a stable sorting algorithm, the best case is that the array is ordered, you don’t need to exchange elements, you only need to go 1 time, the time complexity is O(n); In the worst case, the array is in reverse order, and you swap elements every time, n minus 1 times, and the time is O(n ^ 2); In the average case, the time complexity is O(n ^ 2) based on the above calculation; During element exchange, if the method of introducing intermediate variables is adopted, then the intermediate variables occupy a space. The above code adopts the method of bit operation to carry out element exchange without introducing intermediate variables. No matter which method is adopted, the space complexity is O(1).

Average time complexity: O(n ^ 2)

Best time complexity: O(n)

Worst time complexity: O(n ^ 2)

Space complexity: O(1)

The resources

Bubble Sort GIFs from: Bubble Sort

The original link

Summary of algorithms – Bubble Sort