Thuật toán sắp xếp nổi bọt (Bubble Sort)

Giới thiệu

Bubble Sort (sắp xếp nổi bọt) là thuật toán sắp xếp đơn giản, hoạt động bằng cách liên tục so sánh hai phần tử kề nhau và hoán đổi nếu chúng không đúng thứ tự.

Độ phức tạp

Trường hợp	Độ phức tạp
Tốt nhất	O(n)
Trung bình	O(n²)
Tệ nhất	O(n²)
Bộ nhớ	O(1)

Cài đặt bằng JavaScript

function bubbleSort(arr) {
    const n = arr.length
    for (let i = 0; i < n - 1; i++) {
        let swapped = false
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
                swapped = true
            }
        }
        if (!swapped) break
    }
    return arr
}

console.log(bubbleSort([5, 2, 9, 1, 5, 6]))
// → [1, 2, 5, 5, 6, 9]

Khi nào nên dùng?

• Mảng đầu vào rất nhỏ.
• Khi bạn cần một thuật toán cực kỳ dễ cài đặt để minh hoạ.
• Với dữ liệu thực tế lớn, hãy ưu tiên Quick Sort, Merge Sort hoặc các hàm sắp xếp có sẵn của ngôn ngữ.