What is bubble sort
Bubble sort is a basic commutative sort. The idea is to compare adjacent elements in pairs and swap their positions when one element is greater than the one on the right; when one element is less than or equal to the one on the right, the position does not change.
Bubble sort is a stable sort in which elements of equal value do not disturb the original order. Since the sorting algorithm traverses the elements in each round, a total of (number of elements -1) rounds, the average time complexity is O(n^2).
To do a good job, he must sharpen his tools
Before we talk about bubble sort, let’s set up a simple sort algorithm writing environment that will make it easier to write and test sort algorithms.
SortUtils
A sorting algorithm tool class, which contains some basic operations for sorting algorithm writing and testing.
public class SortUtils {
/** * randomly generates an integer array **@paramSize Array size *@paramRangeL Array left range (inclusive) *@paramRangeR array right range (inclusive) *@returnAn integer array */
public static int[] generateRandomArray(int size, int rangeL, int rangeR) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = (int) (Math.random() * (rangeR - rangeL + 1)) + rangeL;
}
return arr;
}
/** * generates a nearly ordered integer array **@paramSize Array size *@paramSwapTimes scrambles the ordered array *@returnA nearly ordered integer array */
public static int[] generateAlmostOrderlyArray(int size, int swapTimes) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
for (int i = 0; i < swapTimes; i++) {
int index1 = (int) (Math.random() * size);
int index2 = (int) (Math.random() * size);
swap(arr, index1, index2);
}
return arr;
}
/** * If an array is ordered, return true for ordered and false for unordered@paramArray arr *@returnIs the order */
public static boolean isOrderly(int[] arr) {
return isOrderAsc(arr) || isOrderDesc(arr);
}
/** * If an array is ordered, return true for ordered and false for unordered@paramArray arr *@returnIs the order */
private static boolean isOrderAsc(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false; }}return true;
}
/** * If an array is ordered in reverse order, return true for ordered and false for unordered@paramArray arr *@returnIs the order */
private static boolean isOrderDesc(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
if (arr[i] > arr[i - 1]) {
return false; }}return true;
}
/** * copy an integer array **@paramArr integer array *@returnNew integer array */
public static int[] copyIntArray(int[] arr) {
int[] copyArr = new int[arr.length];
System.arraycopy(arr, 0, copyArr, 0, arr.length);
return copyArr;
}
/** * Swap the positions of the two indexes in the array **@paramArr integer array *@paramI The first index *@paramJ Second index */
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/** * prints the array **@paramArr integer array */
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + "\t"); } System.out.println(); }}Copy the codeSort functional interface
A functional interface based on JDK8 Lambda feature, so the sort algorithm environment is built based on JDK8+ version.
@FunctionalInterface
public interface Sort {
/** * sort by **@paramArray arr * /
void sort(int[] arr);
}
Copy the codeSortRunner
SortRunner has methods for running the Sort functional interface, and you can write specific operations under the class’s methods to aid in sorting algorithm writing and testing.
public class SortRunner {
/** * How to run the sorting algorithm **@paramArr an array *@paramSort sort function interface */
public static void run(int[] arr, Sort sort) {
System.out.print("Array sort before:");
SortUtils.printArray(arr);
long startTime = System.currentTimeMillis();
sort.sort(arr);
long endTime = System.currentTimeMillis();
if (SortUtils.isOrderly(arr)) {
System.out.print("After sorting the array:");
SortUtils.printArray(arr);
System.out.println("Array sort time is:" + (endTime - startTime) + "毫秒");
} else {
System.out.println("Array sort failed"); } System.out.println(); }}Copy the codeBubble sort
Ordinary bubble sort
Normal bubble sort compares adjacent elements in pairs until all elements are compared
System.out.println("Ordinary bubble sort");
SortRunner.run(SortUtils.generateRandomArray(10000.100.100000),
(arr) -> {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1); }}}});Copy the codeThis is the most common bubble sort and is simple to write and understand, but in some special cases it can waste some performance.
For example, if I sort to n-i, which is going through the array, and I find that the array is already sorted, the rest of i-1 can actually go through without going through.
So we can optimize bubble sort a little bit.
Boolean type variables determine order
The idea of bubble sort is that before each round of the array is iterated, a variable is set to indicate that the array is ordered. If the array is swapped between adjacent elements in that round, the array is still unordered, and if it is not, the array is ordered.
// Boolean type variables determine order optimization bubble sort
System.out.println("Boolean type variables for determining ordered Optimization bubble Sort");
SortRunner.run(SortUtils.generateRandomArray(10000.100.100000),
(arr) -> {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false; }}if (isSorted) {
break; }}});Copy the codeUnordered boundary value
Boolean type variable determines the ordered optimization of bubble sort, which essentially reduces the number of rounds of bubble sort. Bubble sort can be polling <= n-1 times, but the number of elements exchanged in each round is still fixed.
But sometimes, every time you swap elements, maybe n minus I times, the elements at the end of the array are already sorted, and it’s useless to keep going back and forth.
So to solve this situation, you can use unordered boundaries to optimize bubble sorting
// Unordered boundary values optimize bubble sort
System.out.println("Unordered boundary value optimized bubble sort");
SortRunner.run(SortUtils.generateRandomArray(10000.100.100000),
(arr) -> {
int lastExchangeIndex = 0;
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break; }}});Copy the codeCocktail ordering
In some special cases, such as sorting nearly ordered arrays, consider using cocktail sort to sort data.
The idea of cocktail sort is to compare and exchange elements using a two-way traversal during bubble sort comparisons and swaps.
// Cocktail sort
System.out.println("Cocktail sort.");
SortRunner.run(SortUtils.generateRandomArray(10000.100.100000),
(arr) -> {
for (int i = 0; i < arr.length / 2; i++) {
// Odd rounds, sorted from left to right
boolean isSorted = true;
for (int j = i; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false; }}if (isSorted) {
break;
}
// Even round, from right to left after all
isSorted = true;
for (int j = arr.length - i - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
SortUtils.swap(arr, j, j - 1);
isSorted = false; }}if (isSorted) {
break; }}});Copy the codeLeft and right unordered boundary values
Cocktail sorting can also be optimized by using the method of unordered boundary values, but because cocktail sorting is bidirectional, there are also two unordered values.
// The left and right unordered boundary values optimize cocktail sorting
System.out.println("Left and right unordered boundary values optimize cocktail sorting.");
SortRunner.run(SortUtils.generateRandomArray(10000.100.100000),
(arr) -> {
// The last index on the left to swap elements
int leftExchangeIndex = 0;
/ / the left border
int leftSortBorder = leftExchangeIndex;
// The last index on the right to swap elements
int rightExchangeIndex = arr.length - 1;
/ / right border
int rightSortBorder = rightExchangeIndex;
for (int i = 0; i < arr.length / 2; i++) {
// Odd rounds, sorted from left to right
boolean isSorted = true;
for (int j = i; j < rightSortBorder; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false;
rightExchangeIndex = j;
}
}
rightSortBorder = rightExchangeIndex;
if (isSorted) {
break;
}
// Even round, from right to left after all
isSorted = true;
for (int j = arr.length - i - 1; j > leftSortBorder; j--) {
if (arr[j] < arr[j - 1]) {
SortUtils.swap(arr, j, j - 1);
isSorted = false;
leftExchangeIndex = j;
}
}
leftSortBorder = leftExchangeIndex;
if (isSorted) {
break; }}});Copy the codeEfficiency of cocktail sorting
Array length: 100000
| Bubble sort | Cocktail ordering | |
|---|---|---|
| A disorderly array | 27412 milliseconds | 12868 milliseconds |
| The approximate order | 13962 milliseconds | 43 milliseconds |
The above test data is only a simple test, please test by yourself in specific cases. In addition, if the length of the sorting number is too long, it is recommended to modify sorTrunner.run () to remove some useless operation steps and reduce the total length of the sorting test
The last
In this paper, making github.com/herenpeng/c… Welcome Star.