1. Introduction
In computer science, a sorting algorithm is an algorithm that arranges a set of data items in a certain order. Sorting algorithms play a crucial role in data processing and they are widely used in various software and systems. Bubble Sort is a simple sorting algorithm that repeatedly traverses the sequence to be sorted, compares two elements at a time, and swaps them if they are incorrect. The work of traversing the sequence is repeated until no exchange is needed, that is, the sequence has been sorted.
2. The basic idea of bubble sorting
The basic idea of bubble sorting is:Through comparison and exchange between adjacent elements, the smaller elements in each pair of adjacent elements are "floated" to the front and the larger elements are "sinked" to the back. This process is similar to the process of bubbles in water gradually rising to the surface of the water, hence the name "bubble sorting".
3. Algorithm steps for bubble sorting
- Comparing adjacent elements. If the first one is bigger than the second one, exchange them for the two.
- Do the same work for each pair of adjacent elements, from the beginning of the first pair to the end of the last pair. After this step is completed, the last element will be the largest number.
- For all elementsRepeat the above steps, except for the last one.
- Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers that need to be compared.
4. Time complexity and spatial complexity of bubble sorting
1. Time complexity:
- The best case: The input sequence is already ordered, and you only need to traverse it once at this time, and the time complexity is O(n).
- Worst case: The input sequence is completely reversed, and n-1 times need to be traversed at this time. Each traversal requires n-i comparisons and possible exchanges (i is the number of times the current traversal), so the total time complexity is O(n^2).
- Average case: The time complexity is O(n^2).
2. Space complexity:
- Bubble sorting only requires an extra space to store temporary variables (for exchange), so the space complexity is O(1).
5. Implementation of Java code for bubble sorting
Here is a bubbling sorting Java code implementation:
public class BubbleSort {
// Bubble sorting function public static void bubbleSort(int[] arr) {
int n = ;
for (int i = 0; i < n - 1; i++) { // Outer loop controls the number of sorting strokes for (int j = 0; j < n - i - 1; j++) { // Inner loop controls how many times each time is sorted // If the current element is greater than the next element, swap them if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// Output the sorting result of the current stroke (optional) // printArray(arr);
}
}
// Print array (helping function) public static void printArray(int[] arr) {
int n = ;
for (int i = 0; i < n; ++i) {
(arr[i] + " ");
}
();
}
// Main function public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
("Original array:");
printArray(arr);
bubbleSort(arr);
("Bubble-sorted array:");
printArray(arr);
}
}
6. Optimization of bubble sorting
Although the basic idea of bubble sorting is simple and easy to understand, it is less efficient when dealing with large data sets. Therefore, we can do some optimizations to bubble sort:
- Tag exchange: If no exchange occurs during a traversal, it means that the array is already ordered and the sorting can be ended in advance.
public static void optimizedBubbleSort(int[] arr) {
int n = ;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no exchange occurs, it means that the array is already ordered and can be completed in advance if (!swapped) {
break;
}
}
}
- Cocktail sorting(Cocktail Sort): Cocktail sorting is a variant of bubble sorting. In each traversal, it first bubbling sorting from left to right to ensure that the maximum value is "broadened" to the right, and then bubbling sorting from right to left to ensure that the minimum value is "broadened" to the left. This strategy can reduce the number of comparisons slightly, but in most cases performance improvements are not significant.
7. Applicable scenarios for bubble sorting
Although bubble sorting is not efficient, it still has its uses in certain specific scenarios:
Small dataset sorting: The performance of bubble sorting is acceptable for smaller data sets and is often used as teaching examples because of its simple implementation, easy to understand and implement.
Scenarios with high stability requirements: Bubble sorting is a stable sorting algorithm, that is, the relative order of equal elements remains unchanged after sorting. In some scenarios where equal elements need to be kept in relative order, bubble sorting is a good choice.
Embedded systems or low-level programming: In resource-constrained embedded systems or low-level programming environments, the simplicity of bubble sorting may make it the preferred algorithm because it does not require additional data structures or complex operations.
8. Pros and cons of bubble sorting
advantage:
Simple and easy to understand: The algorithm logic of bubble sort is very simple, easy to understand and implement, so it is often used as an introductory algorithm for learning sorting algorithms.
stability: Bubble sorting is a stable sorting algorithm, that is, equal elements maintain their original relative order after sorting.
High space efficiency: Bubble sort only requires an extra space to store temporary variables (if swap is required), so it has very low space complexity, which is O(1).
shortcoming:
Low time efficiency: The time complexity of bubble sorting is high, especially when the data set to be sorted is very inefficient. Its average time complexity and worst time complexity are both O(n^2), where n is the number of data elements to be sorted.
Not suitable for large data sets: Due to the time efficiency of bubble sorting, it is not suitable for sorting large data sets. For large data sets, more efficient sorting algorithms should be selected, such as merge sorting, quick sorting or heap sorting, etc.
9. Variants of bubble sorting
In addition to the above mentioned Cocktail Sort, there are some other variants of Bubble Sort:
Odd-Even Sort: Parity sort is a variant of bubble sorting that reduces the number of comparisons by alternating left to right and right to left. Specifically, it first performs a left-to-right bubble sort, "broad" the largest element to the rightmost right; then performs a right-to-left bubble sort, "broad" the smallest element to the leftmost left; then repeats this process, but only processes the unsorted elements at a time.
Improved bubble sorting: Improved bubble sorting adds a flag to the algorithm to determine whether there is an exchange during this sorting process. If no exchange occurs, it means that the array is already ordered and the sorting can be ended in advance. This optimization can reduce unnecessary traversal times and improve the efficiency of the algorithm.
10. Application scenarios for bubble sorting
Although bubble sorting is not as efficient as other sorting algorithms, it still has its application value in some specific scenarios:
Sorting small datasets: For small datasets, the efficiency of bubble sorting is acceptable. Due to its simplicity and stability, it is often used to sort small datasets.
Scenarios with high stability requirements: In some scenarios where equal elements need to be kept in relative order, bubble sorting is a good choice. For example, when sorting student grades, if the two students have the same grades, we want their order to remain unchanged after sorting, and then we can use bubble sorting.
Embedded systems or low-level programming: In resource-constrained embedded systems or low-level programming environments, the simplicity of bubble sorting may make it the preferred algorithm. Since it does not require additional data structures or complex operations, it is ideal for use in these environments.
11. Summary
Bubble sorting is a simple and intuitive sorting algorithm that implements sorting through comparison and exchange between adjacent elements. Although it is not as efficient as other sorting algorithms, it still has its application value in certain specific scenarios. In practical applications, we should choose the appropriate sorting algorithm based on specific needs and data characteristics. At the same time, we can also improve the efficiency of bubble sorting through some optimization strategies, such as mark exchange and cocktail sorting.
This is the end of this article about the detailed explanation of Java bubble sorting. For more detailed explanation of Java bubble sorting, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!