11.3 Bubble sort¶
Bubble sort sorts by repeatedly comparing and swapping adjacent elements. The process resembles bubbles rising from the bottom to the top, which gives the algorithm its name.
As shown below, we can simulate bubbling through swaps. Scan from the left end of the array to the right, comparing each pair of adjacent elements. If the left element is greater than the right, swap them. After the scan, the largest element has moved to the far right.







Figure 11-4 Simulating bubbling through element swaps
11.3.1 Algorithm steps¶
For an array of length \(n\), bubble sort proceeds as shown below.
- First, perform a bubbling pass over all \(n\) elements, moving the largest element to its correct position.
- Next, perform a pass over the remaining \(n - 1\) elements, moving the second-largest element to its correct position.
- Continue in this way. After \(n - 1\) passes, the largest \(n - 1\) elements are all in their correct positions.
- The one remaining element must be the smallest and needs no further sorting. The array is now sorted.

Figure 11-5 The bubble sort process
An implementation follows:
def bubble_sort(nums: list[int]):
"""Bubble sort"""
n = len(nums)
# Outer loop: the unsorted range is [0, i]
for i in range(n - 1, 0, -1):
# Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
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: the unsorted range is [0, i]
for (int i = nums.size() - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
// Use the std::swap() function here
swap(nums[j], nums[j + 1]);
}
}
}
}
/* Bubble sort */
void bubbleSort(int[] nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.length - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
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;
}
}
}
}
/* Bubble sort */
void BubbleSort(int[] nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
}
}
}
}
/* Bubble sort */
func bubbleSort(nums []int) {
// Outer loop: the unsorted range is [0, i]
for i := len(nums) - 1; i > 0; i-- {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j := 0; j < i; j++ {
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 */
func bubbleSort(nums: inout [Int]) {
// Outer loop: the unsorted range is [0, i]
for i in nums.indices.dropFirst().reversed() {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j in 0 ..< i {
if nums[j] > nums[j + 1] {
// Swap nums[j] and nums[j + 1]
nums.swapAt(j, j + 1)
}
}
}
}
/* Bubble sort */
function bubbleSort(nums) {
// Outer loop: the unsorted range is [0, i]
for (let i = nums.length - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
}
/* Bubble sort */
function bubbleSort(nums: number[]): void {
// Outer loop: the unsorted range is [0, i]
for (let i = nums.length - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
}
/* Bubble sort */
void bubbleSort(List<int> nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.length - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
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;
}
}
}
}
/* Bubble sort */
fn bubble_sort(nums: &mut [i32]) {
// Outer loop: the unsorted range is [0, i]
for i in (1..nums.len()).rev() {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j in 0..i {
if nums[j] > nums[j + 1] {
// Swap nums[j] and nums[j + 1]
nums.swap(j, j + 1);
}
}
}
}
/* Bubble sort */
void bubbleSort(int nums[], int size) {
// Outer loop: the unsorted range is [0, i]
for (int i = size - 1; i > 0; i--) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
/* Bubble sort */
fun bubbleSort(nums: IntArray) {
// Outer loop: the unsorted range is [0, i]
for (i in nums.size - 1 downTo 1) {
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (j in 0..<i) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
val temp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = temp
}
}
}
}
### Bubble sort ###
def bubble_sort(nums)
n = nums.length
# Outer loop: the unsorted range is [0, i]
for i in (n - 1).downto(1)
# Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j in 0...i
if nums[j] > nums[j + 1]
# Swap nums[j] and nums[j + 1]
nums[j], nums[j + 1] = nums[j + 1], nums[j]
end
end
end
end
Visualize execution
11.3.2 Improving efficiency¶
If a bubbling pass performs no swaps, the array is already sorted and we can return immediately. We can therefore add a variable flag to detect this situation and stop as soon as it occurs.
With this optimization, the worst-case and average time complexities remain \(O(n^2)\). However, a fully sorted input achieves the best-case time complexity of \(O(n)\).
def bubble_sort_with_flag(nums: list[int]):
"""Bubble sort (flag optimization)"""
n = len(nums)
# Outer loop: the unsorted range is [0, i]
for i in range(n - 1, 0, -1):
flag = False # Initialize the flag
# Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
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 that a swap occurred
if not flag:
break # Exit immediately if this pass made no swaps
/* Bubble sort (flag optimization)*/
void bubbleSortWithFlag(vector<int> &nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.size() - 1; i > 0; i--) {
bool flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
// Use the std::swap() function here
swap(nums[j], nums[j + 1]);
flag = true; // Record that a swap occurred
}
}
if (!flag)
break; // Exit immediately if this pass made no swaps
}
}
/* Bubble sort (flag optimization) */
void bubbleSortWithFlag(int[] nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.length - 1; i > 0; i--) {
boolean flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
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 that a swap occurred
}
}
if (!flag)
break; // Exit immediately if this pass made no swaps
}
}
/* Bubble sort (flag optimization)*/
void BubbleSortWithFlag(int[] nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
bool flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
flag = true; // Record that a swap occurred
}
}
if (!flag) break; // Exit immediately if this pass made no swaps
}
}
/* Bubble sort (flag optimization)*/
func bubbleSortWithFlag(nums []int) {
// Outer loop: the unsorted range is [0, i]
for i := len(nums) - 1; i > 0; i-- {
flag := false // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j := 0; j < i; j++ {
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 that a swap occurred
}
}
if flag == false { // Exit immediately if this pass made no swaps
break
}
}
}
/* Bubble sort (flag optimization)*/
func bubbleSortWithFlag(nums: inout [Int]) {
// Outer loop: the unsorted range is [0, i]
for i in nums.indices.dropFirst().reversed() {
var flag = false // Initialize the flag
for j in 0 ..< i {
if nums[j] > nums[j + 1] {
// Swap nums[j] and nums[j + 1]
nums.swapAt(j, j + 1)
flag = true // Record that a swap occurred
}
}
if !flag { // Exit immediately if this pass made no swaps
break
}
}
}
/* Bubble sort (flag optimization)*/
function bubbleSortWithFlag(nums) {
// Outer loop: the unsorted range is [0, i]
for (let i = nums.length - 1; i > 0; i--) {
let flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = true; // Record that a swap occurred
}
}
if (!flag) break; // Exit immediately if this pass made no swaps
}
}
/* Bubble sort (flag optimization)*/
function bubbleSortWithFlag(nums: number[]): void {
// Outer loop: the unsorted range is [0, i]
for (let i = nums.length - 1; i > 0; i--) {
let flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
let tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = true; // Record that a swap occurred
}
}
if (!flag) break; // Exit immediately if this pass made no swaps
}
}
/* Bubble sort (flag optimization)*/
void bubbleSortWithFlag(List<int> nums) {
// Outer loop: the unsorted range is [0, i]
for (int i = nums.length - 1; i > 0; i--) {
bool flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
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 that a swap occurred
}
}
if (!flag) break; // Exit immediately if this pass made no swaps
}
}
/* Bubble sort (flag optimization) */
fn bubble_sort_with_flag(nums: &mut [i32]) {
// Outer loop: the unsorted range is [0, i]
for i in (1..nums.len()).rev() {
let mut flag = false; // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j in 0..i {
if nums[j] > nums[j + 1] {
// Swap nums[j] and nums[j + 1]
nums.swap(j, j + 1);
flag = true; // Record that a swap occurred
}
}
if !flag {
break; // Exit immediately if this pass made no swaps
};
}
}
/* Bubble sort (flag optimization)*/
void bubbleSortWithFlag(int nums[], int size) {
// Outer loop: the unsorted range is [0, i]
for (int i = size - 1; i > 0; i--) {
bool flag = false;
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = true;
}
}
if (!flag)
break;
}
}
/* Bubble sort (flag optimization) */
fun bubbleSortWithFlag(nums: IntArray) {
// Outer loop: the unsorted range is [0, i]
for (i in nums.size - 1 downTo 1) {
var flag = false // Initialize the flag
// Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for (j in 0..<i) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
val temp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = temp
flag = true // Record that a swap occurred
}
}
if (!flag) break // Exit immediately if this pass made no swaps
}
}
### Bubble sort (flag optimization)###
def bubble_sort_with_flag(nums)
n = nums.length
# Outer loop: the unsorted range is [0, i]
for i in (n - 1).downto(1)
flag = false # Initialize the flag
# Inner loop: move the largest element in the unsorted range [0, i] to its right end through swaps
for j in 0...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 that a swap occurred
end
end
break unless flag # Exit immediately if this pass made no swaps
end
end
Visualize execution
11.3.3 Algorithm properties¶
- Time complexity: \(O(n^2)\); adaptive. Successive passes traverse \(n - 1\), \(n - 2\), \(\dots\), \(2\), and \(1\) positions, totaling \((n - 1) n / 2\). With the
flagoptimization, the best-case time complexity is \(O(n)\). - Space complexity: \(O(1)\); in-place. Pointers \(i\) and \(j\) use constant extra space.
- Stable. Equal elements are not swapped during a bubbling pass.