11.3 Bubble sort¶
Bubble sort works by continuously comparing and swapping adjacent elements. This process is like bubbles rising from the bottom to the top, hence the name "bubble sort."
As shown in Figure 11-4, the bubbling process can be simulated using element swaps: start from the leftmost end of the array and move right, comparing each pair of adjacent elements. If the left element is greater than the right element, swap them. After the traversal, the largest element will have bubbled up to the rightmost end of the array.
Figure 11-4 Simulating bubble process using element swap
11.3.1 Algorithm process¶
Assume the array has length \(n\). The steps of bubble sort are shown in Figure 11-5:
- First, perform one "bubble" pass on \(n\) elements, swapping the largest element to its correct position.
- Next, perform a "bubble" pass on the remaining \(n - 1\) elements, swapping the second largest element to its correct position.
- Continue in this manner; after \(n - 1\) such passes, the largest \(n - 1\) elements will have been moved to their correct positions.
- The only remaining element must be the smallest, so no further sorting is required. At this point, the array is sorted.
Figure 11-5 Bubble sort process
Example code is as follows:
def bubble_sort(nums: list[int]):
"""Bubble sort"""
n = len(nums)
# Outer loop: unsorted range is [0, i]
for i in range(n - 1, 0, -1):
# Inner loop: swap the largest element in the unsorted range [0, i] to the right end of the range
for j in range(i):
if nums[j] > nums[j + 1]:
# Swap nums[j] and nums[j + 1]
nums[j], nums[j + 1] = nums[j + 1], nums[j]
/* Bubble sort */
void bubbleSort(vector<int> &nums) {
// Outer loop: unsorted range is [0, i]
for (int i = nums.size() - 1; i > 0; i--) {
// Inner loop: swap the largest element in the unsorted range [0, i] to the right end of the range
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
// Here, the std
swap(nums[j], nums[j + 1]);
}
}
}
}
/* Bubble sort */
void bubbleSort(int[] nums) {
// Outer loop: unsorted range is [0, i]
for (int i = nums.length - 1; i > 0; i--) {
// Inner loop: swap the largest element in the unsorted range [0, i] to the right end of the range
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
}
11.3.2 Efficiency optimization¶
If no swaps occur during a round of "bubbling," the array is already sorted, so we can return immediately. To detect this, we can add a flag variable; whenever no swaps are made in a pass, we set the flag and return early.
Even with this optimization, the worst time complexity and average time complexity of bubble sort remains \(O(n^2)\). However, if the input array is already sorted, the best-case time complexity can be as low as \(O(n)\).
def bubble_sort_with_flag(nums: list[int]):
"""Bubble sort (optimized with flag)"""
n = len(nums)
# Outer loop: unsorted range is [0, i]
for i in range(n - 1, 0, -1):
flag = False # Initialize flag
# Inner loop: swap the largest element in the unsorted range [0, i] to the right end of the range
for j in range(i):
if nums[j] > nums[j + 1]:
# Swap nums[j] and nums[j + 1]
nums[j], nums[j + 1] = nums[j + 1], nums[j]
flag = True # Record swapped elements
if not flag:
break # If no elements were swapped in this round of "bubbling", exit
/* Bubble sort (optimized with flag)*/
void bubbleSortWithFlag(vector<int> &nums) {
// Outer loop: unsorted range is [0, i]
for (int i = nums.size() - 1; i > 0; i--) {
bool flag = false; // Initialize flag
// Inner loop: swap the largest element in the unsorted range [0, i] to the right end of the range
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
// Here, the std
swap(nums[j], nums[j + 1]);
flag = true; // Record swapped elements
}
}
if (!flag)
break; // If no elements were swapped in this round of "bubbling", exit
}
}
/* Bubble sort (optimized with flag) */
void bubbleSortWithFlag(int[] nums) {
// Outer loop: unsorted range is [0, i]
for (int i = nums.length - 1; i > 0; i--) {
boolean flag = false; // Initialize flag
// Inner loop: swap the largest element in the unsorted range [0, i] to the right end of the range
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = true; // Record swapped elements
}
}
if (!flag)
break; // If no elements were swapped in this round of "bubbling", exit
}
}
11.3.3 Algorithm characteristics¶
- Time complexity of \(O(n^2)\), adaptive sorting. Each round of "bubbling" traverses array segments of length \(n - 1\), \(n - 2\), \(\dots\), \(2\), \(1\), which sums to \((n - 1) n / 2\). With a
flagoptimization, the best-case time complexity can reach \(O(n)\) when the array is already sorted. - Space complexity of \(O(1)\), in-place sorting. Only a constant amount of extra space is used by pointers \(i\) and \(j\).
- Stable sorting. Because equal elements are not swapped during "bubbling," their original order is preserved, making this a stable sort.