Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 11.3 Bubble Sort

Bubble sort sorts an array by continuously comparing and swapping adjacent elements. This process resembles 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: starting from the leftmost end of the array and traversing to the right, compare each pair of adjacent elements, and if "left element > right element", swap them. After the traversal is complete, the largest element is moved to the rightmost end of the array.

<1><2><3><4><5><6><7>

Figure 11-4 Simulating bubble sort using element swaps

## 11.3.1 Algorithm Flow

Assume the array has length \(n\). The steps of bubble sort are shown in Figure 11-5.

1. First, perform "bubbling" on \(n\) elements, swapping the largest element of the array to its correct position.
2. Next, perform "bubbling" on the remaining \(n - 1\) elements, swapping the second largest element to its correct position.
3. And so on. After \(n - 1\) rounds of "bubbling", the largest \(n - 1\) elements have all been swapped to their correct positions.
4. The only remaining element must be the smallest element, requiring no sorting, so the array sorting is complete.

Figure 11-5 Bubble sort flow

Example code is as follows:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
bubble_sort.py

    def bubble_sort(nums: list[int]):
        """Bubble sort"""
        n = len(nums)
        # Outer loop: unsorted interval is [0, i]
        for i in range(n - 1, 0, -1):
            # Inner loop: swap the largest element in the unsorted interval [0, i] to the rightmost end of the interval
            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.cpp

    /* 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 rightmost end of that range
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // Swap nums[j] and nums[j + 1]
                    // Using std::swap() function here
                    swap(nums[j], nums[j + 1]);
                }
            }
        }
    }

bubble_sort.java

    /* 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 rightmost end of that 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;
                }
            }
        }
    }

bubble_sort.cs

    /* 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 rightmost end of that range
            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.go

    /* Bubble sort */
    func bubbleSort(nums []int) {
        // Outer loop: unsorted range is [0, i]
        for i := len(nums) - 1; i > 0; i-- {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.swift

    /* Bubble sort */
    func bubbleSort(nums: inout [Int]) {
        // Outer loop: unsorted range is [0, i]
        for i in nums.indices.dropFirst().reversed() {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.js

    /* Bubble sort */
    function bubbleSort(nums) {
        // Outer loop: unsorted range is [0, i]
        for (let i = nums.length - 1; i > 0; i--) {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.ts

    /* Bubble sort */
    function bubbleSort(nums: number[]): void {
        // Outer loop: unsorted range is [0, i]
        for (let i = nums.length - 1; i > 0; i--) {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.dart

    /* Bubble sort */
    void bubbleSort(List<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 rightmost end of that 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;
          }
        }
      }
    }

bubble_sort.rs

    /* Bubble sort */
    fn bubble_sort(nums: &mut [i32]) {
        // Outer loop: unsorted range is [0, i]
        for i in (1..nums.len()).rev() {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.c

    /* Bubble sort */
    void bubbleSort(int nums[], int size) {
        // Outer loop: unsorted range is [0, i]
        for (int i = size - 1; i > 0; i--) {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.kt

    /* Bubble sort */
    fun bubbleSort(nums: IntArray) {
        // Outer loop: unsorted range is [0, i]
        for (i in nums.size - 1 downTo 1) {
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.rb

    ### Bubble sort ###
    def bubble_sort(nums)
      n = nums.length
      # Outer loop: unsorted range is [0, i]
      for i in (n - 1).downto(1)
        # Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
        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

## 11.3.2 Efficiency Optimization

We can observe that if no swaps occur during a round of "bubbling", the array is already sorted and the algorithm can return immediately. Therefore, we can add a flag `flag` to detect this situation and terminate as soon as it occurs.

After this optimization, the worst-case and average-case time complexities of bubble sort remain \(O(n^2)\); however, when the input array is already sorted, the best-case time complexity becomes \(O(n)\).

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
bubble_sort.py

    def bubble_sort_with_flag(nums: list[int]):
        """Bubble sort (flag optimization)"""
        n = len(nums)
        # Outer loop: unsorted interval is [0, i]
        for i in range(n - 1, 0, -1):
            flag = False  # Initialize flag
            # Inner loop: swap the largest element in the unsorted interval [0, i] to the rightmost end of the interval
            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 element swap
            if not flag:
                break  # No elements were swapped in this round of "bubbling", exit directly

bubble_sort.cpp

    /* Bubble sort (flag optimization)*/
    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 rightmost end of that range
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // Swap nums[j] and nums[j + 1]
                    // Using std::swap() function here
                    swap(nums[j], nums[j + 1]);
                    flag = true; // Record element swap
                }
            }
            if (!flag)
                break; // No elements were swapped in this round of "bubbling", exit directly
        }
    }

bubble_sort.java

    /* Bubble sort (flag optimization) */
    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 rightmost end of that 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 element swap
                }
            }
            if (!flag)
                break; // No elements were swapped in this round of "bubbling", exit directly
        }
    }

bubble_sort.cs

    /* Bubble sort (flag optimization) */
    void BubbleSortWithFlag(int[] nums) {
        // Outer loop: unsorted range is [0, i]
        for (int i = nums.Length - 1; i > 0; i--) {
            bool flag = false; // Initialize flag
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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 element swap
                }
            }
            if (!flag) break;     // No elements were swapped in this round of "bubbling", exit directly
        }
    }

bubble_sort.go

    /* Bubble sort (flag optimization) */
    func bubbleSortWithFlag(nums []int) {
        // Outer loop: unsorted range is [0, i]
        for i := len(nums) - 1; i > 0; i-- {
            flag := false // Initialize flag
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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 element swap
                }
            }
            if flag == false { // No elements were swapped in this round of "bubbling", exit directly
                break
            }
        }
    }

bubble_sort.swift

    /* Bubble sort (flag optimization) */
    func bubbleSortWithFlag(nums: inout [Int]) {
        // Outer loop: unsorted range is [0, i]
        for i in nums.indices.dropFirst().reversed() {
            var flag = false // Initialize 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 element swap
                }
            }
            if !flag { // No elements were swapped in this round of "bubbling", exit directly
                break
            }
        }
    }

bubble_sort.js

    /* Bubble sort (flag optimization) */
    function bubbleSortWithFlag(nums) {
        // Outer loop: unsorted range is [0, i]
        for (let i = nums.length - 1; i > 0; i--) {
            let flag = false; // Initialize flag
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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 element swap
                }
            }
            if (!flag) break; // No elements were swapped in this round of "bubbling", exit directly
        }
    }

bubble_sort.ts

    /* Bubble sort (flag optimization) */
    function bubbleSortWithFlag(nums: number[]): void {
        // Outer loop: unsorted range is [0, i]
        for (let i = nums.length - 1; i > 0; i--) {
            let flag = false; // Initialize flag
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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 element swap
                }
            }
            if (!flag) break; // No elements were swapped in this round of "bubbling", exit directly
        }
    }

bubble_sort.dart

    /* Bubble sort (flag optimization) */
    void bubbleSortWithFlag(List<int> nums) {
      // Outer loop: unsorted range is [0, i]
      for (int i = nums.length - 1; i > 0; i--) {
        bool flag = false; // Initialize flag
        // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that 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 element swap
          }
        }
        if (!flag) break; // No elements were swapped in this round of "bubbling", exit directly
      }
    }

bubble_sort.rs

    /* Bubble sort (flag optimization) */
    fn bubble_sort_with_flag(nums: &mut [i32]) {
        // Outer loop: unsorted range is [0, i]
        for i in (1..nums.len()).rev() {
            let mut flag = false; // Initialize flag
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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 element swap
                }
            }
            if !flag {
                break; // No elements were swapped in this round of "bubbling", exit directly
            };
        }
    }

bubble_sort.c

    /* Bubble sort (flag optimization) */
    void bubbleSortWithFlag(int nums[], int size) {
        // Outer loop: unsorted range is [0, i]
        for (int i = size - 1; i > 0; i--) {
            bool flag = false;
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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.kt

    /* Bubble sort (flag optimization) */
    fun bubbleSortWithFlag(nums: IntArray) {
        // Outer loop: unsorted range is [0, i]
        for (i in nums.size - 1 downTo 1) {
            var flag = false // Initialize flag
            // Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
            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 element swap
                }
            }
            if (!flag) break // No elements were swapped in this round of "bubbling", exit directly
        }
    }

bubble_sort.rb

    ### Bubble sort (flag optimization) ###
    def bubble_sort_with_flag(nums)
      n = nums.length
      # Outer loop: unsorted range is [0, i]
      for i in (n - 1).downto(1)
        flag = false # Initialize flag

        # Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end of that range
        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 element swap
          end
        end

        break unless flag # No elements were swapped in this round of "bubbling", exit directly
      end
    end

## 11.3.3 Algorithm Characteristics

- Time complexity is \(O(n^2)\); adaptive: In successive rounds of "bubbling", the traversed portion of the array has lengths \(n - 1\), \(n - 2\), \(\dots\), \(2\), \(1\), for a total of \((n - 1) n / 2\). After introducing the `flag` optimization, the best-case time complexity can reach \(O(n)\).
- Space complexity of \(O(1)\), in-place sorting: Pointers \(i\) and \(j\) use a constant amount of extra space.
- Stable sorting: Equal elements are not swapped during "bubbling".

##### Feel free to drop your insights, questions or suggestions