Bài giải thích miễn phí · Video · Code · Trắc nghiệm

Sắp xếp nổi bọt (Bubble Sort)

Quét qua mảng, đổi chỗ hai phần tử kề nhau nếu sai thứ tự, để mỗi lượt giá trị lớn nhất nổi lên cuối. Bản sắp xếp tại chỗ, ổn định, dừng ngay khi một lượt không đổi chỗ lần nào: O(n) nếu đã sắp xếp, O(n²) còn lại.

Độ khó: Dễ
Thời gian: O(n²) worst, O(n) best
Bộ nhớ: O(1)

Tự tay chạy thử Làm trắc nghiệm

Tự tay chạy thử

Chạy từng bước theo nhịp của bạn — đây là Bubble Sort Animation, chạy ngay trên trang.

Lấy code này

Đang chạyBubble Sort Animation

Đang tải bản xem trước…

Cách hoạt động

Ý tưởng, một ví dụ chạy thử, và những bẫy nên tránh.

Ý tưởng

Hình dung một hàng người đang xếp theo chiều cao. Bạn đi dọc hàng, và hễ người bên trái cao hơn người bên phải thì nhờ hai người đổi chỗ cho nhau. Đi hết hàng, người cao nhất đã được "mang" tới tận cuối bên phải, như bọt khí nổi lên mặt nước. Đi lại lần nữa, người cao thứ hai sẽ yên vị cạnh đó. Cứ đi cho tới khi cả một chuyến không phải đổi chỗ lần nào: hàng đã có thứ tự.

Đó là sắp xếp nổi bọt. Nó chỉ nhìn hai phần tử kề nhau và sửa nếu chúng sai thứ tự. Nó chậm, nhưng là thuật toán sắp xếp dễ đọc nhất, nên thường là thuật toán đầu tiên bạn gặp.

Có hai chi tiết giúp bản này gọn gàng:

Mỗi lượt ngắn hơn lượt trước một phần tử. Sau lượt 1, giá trị lớn nhất đã về đúng chỗ; sau lượt 2, hai giá trị lớn nhất đã về đúng chỗ, và cứ thế. Nên vòng lặp trong dừng sớm dần (j + 1 < n - i).
Thoát sớm. Cờ swapped ghi lại việc lượt đó có đổi chỗ gì không. Nếu không, mọi cặp kề nhau đều đã đúng thứ tự, tức cả mảng đã được sắp xếp, và ta dừng.

Chạy thử từng bước

Sắp xếp [5, 2, 8, 1, 7, 3, 6, 4]. Mỗi lượt so sánh các cặp kề nhau từ trái sang phải và đổi chỗ khi phần tử bên trái lớn hơn hẳn.

Lượt	So sánh	Đổi chỗ	Mảng sau lượt
1	7	6	`[2, 5, 1, 7, 3, 6, 4 │ 8]`
2	6	4	`[2, 1, 5, 3, 6, 4 │ 7, 8]`
3	5	3	`[1, 2, 3, 5, 4 │ 6, 7, 8]`
4	4	1	`[1, 2, 3, 4 │ 5, 6, 7, 8]`
5	3	0	`[1, 2, 3, 4 │ 5, 6, 7, 8]`

Thanh dọc đánh dấu phần đã về đúng vị trí cuối cùng. Ở lượt 1, số 8 được nhặt lên tại chỉ số 2 rồi mang tới cuối mảng: nó lần lượt đổi chỗ với 1, 7, 3, 6 và 4. Lượt 5 không đổi chỗ lần nào, swapped vẫn là false, và thuật toán dừng. Tổng cộng 25 lần so sánh và 14 lần đổi chỗ.

Con số 14 không phải ngẫu nhiên: mỗi lần đổi chỗ sửa đúng một nghịch thế (một cặp sai thứ tự), và mảng này có đúng 14 nghịch thế. Sắp xếp nổi bọt đổi chỗ đúng bằng số nghịch thế, không hơn không kém.

Vì sao thuật toán đúng

Sau lượt thứ i, i giá trị lớn nhất nằm ở cuối mảng, đúng thứ tự cuối cùng. Lượt 1 chứng minh điều này cho một giá trị: khi mang giá trị lớn nhất tạm thời sang phải, giá trị lớn hơn luôn thắng ở phép đổi chỗ, nên giá trị lớn nhất toàn mảng không bao giờ bị bỏ lại và dừng ở chỉ số cuối. Mỗi lượt sau lặp lại việc đó trên phần đầu mảng còn lại, ngắn hơn.

Nếu một lượt không đổi chỗ, thì values[j] <= values[j + 1] với mọi cặp kề nhau trong phần đầu đó, đúng là định nghĩa của "đã sắp xếp". Dừng ở đó là an toàn, và chạy hết vòng ngoài cũng an toàn: sau n - 1 lượt chỉ còn một giá trị, và nó không còn chỗ nào khác để đi.

Độ phức tạp

Tệ nhất và trung bình: O(n²). Lượt i làm n - 1 - i phép so sánh, cộng lại là n(n - 1) / 2. Mảng sắp xếp ngược cũng cần chừng đó lần đổi chỗ. Mảng ngẫu nhiên cần khoảng một nửa, nhưng vẫn là bậc hai.
Tốt nhất: O(n). Với mảng đã sắp xếp, lượt đầu không đổi chỗ lần nào và cơ chế thoát sớm dừng sau n - 1 phép so sánh. Bỏ cờ swapped đi thì sắp xếp nổi bọt luôn là bậc hai.
Bộ nhớ: O(1). Đổi chỗ tại chỗ với một biến tạm.
Ổn định. Phép so sánh là chặt (>), nên hai giá trị bằng nhau không bao giờ bị đổi chỗ và giữ nguyên thứ tự ban đầu. Sắp danh sách người theo thành phố rồi theo tuổi, những người cùng tuổi vẫn nằm theo thứ tự thành phố. Đổi sang >= là mất tính ổn định, lại đổi chỗ thừa vô ích.

Lỗi hay gặp

Quên rằng vòng trong ngắn dần. Cho j chạy tới hết mảng ở mọi lượt vẫn ra kết quả đúng, nhưng so sánh lại cả những giá trị đã về đúng chỗ.
Lệch một đơn vị ở cuối hàng. Vòng trong đọc values[j + 1], nên j phải dừng ở n - i - 2. Trong đoạn code, j + 1 < n - i lo việc đó.
Đặt lại swapped sai chỗ. Phải đặt lại ở đầu mỗi lượt. Nếu chỉ gán một lần bên ngoài vòng ngoài, một lần đổi chỗ ở lượt 1 là đủ để cơ chế thoát sớm không bao giờ chạy.
Dùng >= thay cho >. Vẫn sắp xếp đúng, nhưng đổi chỗ thừa các giá trị bằng nhau và làm mất tính ổn định.
Biến đếm không dấu trong C++. Với std::size_t, n - 1 bị tràn vòng khi mảng rỗng. Vì vậy đoạn code viết cận là i + 1 < n.

Khi nào nên dùng, khi nào không

Dùng để học sắp xếp, để dạy bất biến vòng lặp, hoặc cho mảng rất nhỏ hay gần như đã có thứ tự, khi thoát sớm biến nó thành một lượt duyệt rẻ. Nó cũng tiện khi bạn cần thuật toán ổn định, tại chỗ, đơn giản nhất có thể và tốc độ không quan trọng.

Với khối lượng thật thì đừng. Với một nghìn phần tử, thuật toán bậc hai đã làm cỡ nửa triệu phép so sánh, so với khoảng mười nghìn của sắp xếp trộn hay sắp xếp nhanh. Sắp xếp chèn thường là lựa chọn đơn giản tốt hơn: cũng O(n²) và O(n) ở trường hợp tốt nhất, nhưng ghi dữ liệu ít hơn nhiều. Trong dự án thật, cứ gọi hàm sắp xếp có sẵn của ngôn ngữ.

Biến thể khi phỏng vấn

Cocktail shaker sort. Quét sang phải, rồi sang trái, rồi lại sang phải. Giá trị nhỏ ở gần cuối mảng được kéo sang trái rất nhanh, trong khi nổi bọt thường chỉ dịch được một bước mỗi lượt.
Đếm số lần đổi chỗ. Số lần đổi chỗ kề nhau tối thiểu để sắp xếp một mảng bằng đúng số nghịch thế của nó. Hãy đếm nghịch thế trong O(n log n) bằng sắp xếp trộn thay vì mô phỏng.
Sắp xếp tối đa k lượt, hay tìm phần tử lớn thứ k. Sau k lượt, k giá trị lớn nhất đã về đúng chỗ. Cách này giải bài "k phần tử lớn nhất" trong O(nk), chấp nhận được khi k rất nhỏ.
Mảng này có được sắp xếp sau đúng một lượt không? Một lượt đủ để sắp xếp mảng khi và chỉ khi không giá trị nào phải dịch sang trái quá một vị trí. Câu hỏi kinh điển về việc một lượt nổi bọt làm được gì.

Code

Cùng một thuật toán, từng bước như nhau, bằng 4 ngôn ngữ.

JavaScript

// Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
// Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.

/**
 * Sorts `values` in ascending order, in place.
 * Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
 *
 * @param {number[]} values the array to sort
 * @returns {void}
 */
export function bubbleSort(values) {
  const n = values.length;

  for (let i = 0; i + 1 < n; i++) {
    let swapped = false;

    for (let j = 0; j + 1 < n - i; j++) {
      if (values[j] > values[j + 1]) {
        const tmp = values[j];
        values[j] = values[j + 1];
        values[j + 1] = tmp;
        swapped = true;
      }
    }

    if (!swapped) {
      break; // a whole sweep without a swap: already sorted
    }
  }
}

# Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
# Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.
from typing import List


def bubble_sort(values: List[int]) -> None:
    """Sort values in ascending order, in place.

    Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
    """
    n = len(values)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if values[j] > values[j + 1]:
                tmp = values[j]
                values[j] = values[j + 1]
                values[j + 1] = tmp
                swapped = True

        if not swapped:
            break  # a whole sweep without a swap: already sorted

/**
 * Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
 * Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.
 */
public final class BubbleSort {
    private BubbleSort() {
    }

    /**
     * Sorts values in ascending order, in place.
     * Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
     */
    public static void bubbleSort(int[] values) {
        int n = values.length;

        for (int i = 0; i + 1 < n; i++) {
            boolean swapped = false;

            for (int j = 0; j + 1 < n - i; j++) {
                if (values[j] > values[j + 1]) {
                    int tmp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = tmp;
                    swapped = true;
                }
            }

            if (!swapped) {
                break; // a whole sweep without a swap: already sorted
            }
        }
    }
}

// Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
// Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.
#include <cstddef>
#include <vector>

// Sorts values in ascending order, in place.
// Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
void bubbleSort(std::vector<int>& values) {
    std::size_t n = values.size();

    for (std::size_t i = 0; i + 1 < n; i++) {
        bool swapped = false;

        for (std::size_t j = 0; j + 1 < n - i; j++) {
            if (values[j] > values[j + 1]) {
                int tmp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = tmp;
                swapped = true;
            }
        }

        if (!swapped) {
            break;  // a whole sweep without a swap: already sorted
        }
    }
}

Hỏi về thuật toán này

Kẹt ở bước nào? Hỏi thêm ví dụ hoặc vì sao nó chạy đúng.

Tự kiểm tra

10 câu hỏi nhanh xem bạn đã nắm chưa.

Câu 1 · Sắp xếp nổi bọt chạy một lượt trên [5, 2, 8, 1, 7, 3, 6, 4]. Sau lượt đó mảng trông thế nào?

Làm trắc nghiệm

Dùng ngay trong dự án

Animation
Bubble Sort Animation
Bản tương tác của video ngắn: các cột bắt chéo khi đổi chỗ, đuôi đã sắp xếp dài dần và cú thoát sớm
Miễn phí