Sắp xếp · So sánh · Ổn định

Bubble Sort

Sắp xếp nổi bọt — liên tục hoán đổi hai phần tử kề nhau nếu sai thứ tự. Sau mỗi lượt, phần tử lớn nhất "nổi" lên vị trí đúng ở cuối.

● Easy Best: O(n)Avg/Worst: O(n²)Space: O(1)Stable ✓

Tốc độ

Chưa xử lý Đang so sánh Hoán đổi Đã sắp xong

So sánh0

Hoán đổi0

Lượt0

Nhấn Chạy hoặc Bước kế...

Ý tưởng

Mỗi lượt duyệt từ đầu đến cuối phần chưa sắp, so sánh từng cặp kề nhau a[j] và a[j+1]. Nếu sai thứ tự thì hoán đổi. Sau lượt i, phần tử lớn nhất đã về đúng vị trí ở cuối.

Tối ưu quan trọng: nếu một lượt không có hoán đổi nào → mảng đã sắp xong → dừng sớm, đạt O(n) với mảng đã sắp.

Cài đặt C

#include <stdio.h>
#include <stdbool.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/* Bubble Sort — sắp xếp tăng dần, O(n²) */
void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;

        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
                swapped = true;
            }
        }
        /* Dừng sớm nếu không hoán đổi */
        if (!swapped) break;
    }
}

int main() {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(a) / sizeof(a[0]);
    bubbleSort(a, n);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    /* Output: 3 9 10 27 38 43 82 */
    return 0;
}

Độ phức tạp

Trường hợp	Thời gian	Không gian	Ghi chú
Tốt nhất	O(n)	O(1)	Mảng đã sắp, cờ swapped dừng sớm
Trung bình	O(n²)	O(1)	—
Tệ nhất	O(n²)	O(1)	Mảng sắp ngược (n-1 lượt đầy đủ)

← TrướcFibonacci Tiếp →Selection Sort